1076. 迷宫问题?
输入样例：
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0输出样例：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4题解：
这题和简单的最短路径不同的是，我们需要将路径记录下来，因为BFS所搜索出来的路径本身就是最短路径（这里我就不证了）。因为我们要记录路径，所以我们可以另开一个数组 pre[][] 来记录走到当前点（i，j）的上一步,思路大概就是这样，来看一下代码
AC代码：
#include<iostream>
using namespace std;
#define x first
#define y second
const int N = 1010;
bool st[N][N];
int a[N][N];
typedef pair<int, int> PII;
PII q[N * N];
PII pre[N][N];
int n;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
void bfs(int sx, int sy) {
st[sx][sy] = true;
int hh = 0;
int tt = 0;
q[0] = { sx,sy };
while (hh <= tt) {
PII t = q[hh++];
for (int i = 0; i < 4; i++) {
int ax = t.x + dx[i];
int by = t.y + dy[i];
if (ax < 0 || ax >= n || by < 0 || by >= n) continue;
if (a[ax][by] == 1) continue;
if (st[ax][by]) continue;
q[++tt] = { ax,by };
pre[ax][by] = { t.x,t.y };
st[ax][by] = true;
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
bfs(n - 1, n - 1);
PII end(0, 0);
while (true) {
cout << end.x << " " << end.y << endl;
if (end.x == n - 1 && end.y == n - 1) break;
end = pre[end.x][end.y];
}
return 0;
}188. 武士风度的牛
题解：
直接写代码吧，这几个题都大同小异的
AC代码：
#include<iostream>
using namespace std;
#include<cstring>
int n, m;
const int N = 200;
bool st[N][N];
typedef pair<int, int> PII;
PII q[N * N];
char g[N][N];
int dist[N][N];
#define x first
#define y second
int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
int dy[8] = { 1,2,2,1,-1,-2,-2,-1 };
int bfs() {
int sx, sy;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < +m; j++) {
if (g[i][j] == 'K') {
sx = i, sy = j;
}
}
}
st[sx][sy] = true;
memset(dist, -1, sizeof dist);
dist[sx][sy] = 0;
int hh = 0;
int tt = 0;
q[0] = { sx,sy };
while (hh <= tt) {
PII t = q[hh++];
for (int i = 0; i < 8; i++) {
int ax = t.x + dx[i];
int by = t.y + dy[i];
if (g[ax][by] == 'H') return dist[t.x][t.y] + 1;
if (ax<1 || ax>n || by<1 || by>m) continue;
if (st[ax][by]) continue;
if (g[ax][by] == '*') continue;
st[ax][by] = true;
q[++tt] = { ax,by };
dist[ax][by] = dist[t.x][t.y] + 1;
}
}
return -1;
}
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> g[i] + 1;
}
cout << bfs() << endl;
return 0;
}1100. 抓住那头牛
输入样例：
5 17输出样例：
4题解：
因为只有?+1 -1 *2三种选择。
假设当前在 x 位置
1.当选择? -1 操作时，x-1必须大于等于0
2.当选择?+1 操作时，x+1必须小于等于k
3.当选择 *2 操作时，x*2 必须小于等于k*2
AC代码：
#include<iostream>
using namespace std;
#include<cstring>
int n, k;
const int N = 2e5;
int dist[N];
int q[N];
int bfs() {
memset(dist, -1, sizeof dist);
dist[n] = 0;
q[0] = n;
int hh = 0;
int tt = 0;
while (hh <= tt) {
int t = q[hh++];
if (t == k) return dist[k];
if (t - 1 >= 0 && dist[t - 1] == -1) {
dist[t - 1] = dist[t] + 1;
q[++tt] = t - 1;
}
if (t + 1 <= k && dist[t + 1] == -1) {
dist[t + 1] = dist[t] + 1;
q[++tt] = t + 1;
}
if (t * 2 <= N && dist[t * 2] == -1) {
dist[2 * t] = dist[t] + 1;
q[++tt] = 2 * t;
}
}
return -1;
}
int main() {
cin >> n >> k;
bfs();
cout << dist[k] << endl;
return 0;
}