题一：离开中山路 - 洛谷

这道题就是bfs模板题，走迷宫，求两个点之间的最短距离

#include <iostream>
#include <queue>using namespace std;typedef pair<int, int> PII;
const int N = 1010;
int n;
char g[N][N];
int x1, y1, x2, y2;
int vis[N][N];
queue<PII> q;void bfs()
{q.push({x1 - 1, y1 - 1});int x[] = {-1, 1, 0, 0}, y[] = {0, 0, -1, 1};while(q.size()){auto t = q.front();q.pop();for(int i = 0; i < 4; i ++ ){int a = t.first + x[i], b = t.second + y[i];if(a < 0 || a >= n || b < 0 || b >= n) continue;if(g[a][b] == '1') continue;if(vis[a][b]) continue;vis[a][b] = vis[t.first][t.second] + 1;q.push({a, b});}}}int main()
{cin >> n;for(int i = 0; i < n; i ++ )cin >> g[i];cin >> x1 >> y1 >> x2 >> y2;bfs();cout << vis[x2 - 1][y2 - 1];return 0;
}

题二：马的遍历 - 洛谷

也是差不多，更简单一些，只不过这里马走八方

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;typedef pair<int, int> PII;
const int N = 1010;
int n, m, x, y;
char g[N][N];
int x1, y1, x2, y2;
int vis[N][N];
queue<PII> q;void bfs()
{memset(vis, -1, sizeof vis);q.push({x, y});vis[x][y] = 0;// 马走日int x[] = {2, 2, 1, 1, -1, -1, -2, -2}, y[] = {1, -1, 2, -2, 2, -2, 1, -1};while(q.size()){auto t = q.front();q.pop();for(int i = 0; i < 8; i ++ ){int a = t.first + x[i], b = t.second + y[i];if(a < 1 || a > n || b < 1 || b > m) continue;if(vis[a][b] != -1) continue;vis[a][b] = vis[t.first][t.second] + 1;q.push({a, b});}}}int main()
{cin >> n >> m >> x >> y;bfs();for(int i = 1; i <= n; i ++ ){for(int j = 1; j <= m; j ++ ){cout << vis[i][j] << "    "; }cout << endl;}return 0;
}

题三：血色先锋队 - 洛谷

这道题和上边有所不同的就是，起点不止一个，在一开始都放进队列就好了

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>using namespace std;typedef pair<int, int> PII;
const int N = 510;
int n, m, a, b;
int g[N][N];
vector<PII> res, start;
queue<PII> q;void bfs()
{for(int i = 0; i < start.size(); i ++ ){// cout << start[i].first << ' ' << start[i].second << endl;q.push({start[i].first, start[i].second});g[start[i].first][start[i].second] = 0;}int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};while(q.size()){auto t = q.front();q.pop();for(int i = 0; i < 4; i ++ ){int t1 = t.first + dx[i], t2 = t.second + dy[i];if(t1 < 1 || t1 > n || t2 < 1 || t2 > m) continue;if(g[t1][t2] != -1) continue;g[t1][t2] = g[t.first][t.second] + 1;q.push({t1, t2});}}
}int main()
{cin >> n >> m >> a >> b;for(int i = 1; i <= n; i ++ ){memset(g[i], -1, sizeof g[i]);}for(int i = 0; i < a; i ++ ){int x, y;cin >> x >> y;start.push_back({x, y});}for(int i = 0; i < b; i ++ ){int x, y;cin >> x >> y;res.push_back({x, y});}bfs();// for(int i = 1; i <= n; i ++ )// {//     for(int j = 1; j <= m; j ++ )//         cout << g[i][j] << ' ';//     cout << endl;// }for(int i = 0; i < b; i ++ ){cout << g[res[i].first][res[i].second] << endl;}return 0;
}