A. P1746 离开中山路完全预判啊我一开始就用的dfs没做出来#includebits/stdc.h using namespace std; const int MAXN 1005; int mp[MAXN][MAXN]; bool vis[MAXN][MAXN]; int n; int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; struct Node { int x, y, step; }; int bfs(int sx, int sy, int ex, int ey) { queueNode q; q.push({sx, sy, 0}); vis[sx][sy] true; while (!q.empty()) { Node cur q.front(); q.pop(); if (cur.x ex cur.y ey) { return cur.step; } for (int k 0; k 4; k) { int nx cur.x dx[k]; int ny cur.y dy[k]; if (nx 1 nx n ny 1 ny n) { if (!vis[nx][ny] mp[nx][ny] 0) { vis[nx][ny] true; q.push({nx, ny, cur.step 1}); } } } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n; string s;//用正常的数组输入会超时遇到这种情况可以先用字符串输入再传入数组 for (int i 1; i n; i) { cin s; for (int j 1; j n; j) { mp[i][j] s[j - 1] - 0; } } int x1, y1, x2, y2; cin x1 y1 x2 y2; cout bfs(x1, y1, x2, y2) endl; return 0; }后面的题都是异曲同工之妙换汤不换本P1443 马的遍历老师每个题的题解是专门针对那个题的从代码中的各个条件就看得出来而我的代码是在一种套路上修改的感觉#includebits/stdc.h using namespace std; //我说样例我怎么看不懂结果马要走日-_- const int MAX 405; int dis[MAX][MAX]; int dx[] {2, 1, -1, -2, -2, -1, 1, 2}; int dy[] {1, 2, 2, 1, -1, -2, -2, -1}; int n, m; void bfs(int sx, int sy) { memset(dis, -1, sizeof(dis));//一定要设成-1不然无法跟起点0区分 queuepairint, int q; q.push({sx, sy}); dis[sx][sy] 0; while (!q.empty()) { auto cur q.front(); q.pop(); int x cur.first; int y cur.second; for (int i 0; i 8; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 nx n ny 1 ny m dis[nx][ny] -1) { dis[nx][ny] dis[x][y] 1; q.push({nx, ny}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int x, y; cin n m x y; bfs(x, y); for (int i 1; i n; i) { for (int j 1; j m; j) { cout dis[i][j] ; } cout \n; } return 0; }P1506 拯救 oibh 总部这个题依旧和那个马走日一样啊我一开始没意识到洪水是从四周溢过来的一开始想成之前写的一道题标记外圈的0来得到里面的数量但这道题不能这样#includebits/stdc.h using namespace std; const int MAX 505; char mp[MAX][MAX]; bool vis[MAX][MAX]; int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; int n, m; void bfs(int x, int y) { queuepairint, int q; q.push({x, y}); vis[x][y] true; while (!q.empty()) { auto cur q.front(); q.pop(); int sx cur.first; int sy cur.second; for (int i 0; i 4; i) { int nx sx dx[i]; int ny sy dy[i]; if (nx 0 nx n ny 0 ny m !vis[nx][ny] mp[nx][ny] 0) //因为是一步一步走的遇到星号墙就换方向走不会访问到里面的0所以里面的0就没有vis标记 { vis[nx][ny] true; q.push({nx, ny}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 0; i n; i) { string s; cin s; for (int j 0; j m; j) { mp[i][j] s[j]; } } for (int j 0; j m; j) { if (mp[0][j] 0 !vis[0][j]) bfs(0, j);//第一行洪水涌入 if (mp[n-1][j] 0 !vis[n-1][j]) bfs(n-1, j);//最后一行洪水涌入 } for (int i 0; i n; i) { if (mp[i][0] 0 !vis[i][0]) bfs(i, 0);//第一列洪水涌入 if (mp[i][m-1] 0 !vis[i][m-1]) bfs(i, m-1);//最后一列洪水涌入 } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (mp[i][j] 0 !vis[i][j]) ans; } } cout ans endl; return 0; }P1332 血色先锋队#includebits/stdc.h using namespace std; const int MAX505; int dist[MAX][MAX]; int dx[]{-1,1,0,0}; int dy[]{0,0,-1,1}; queuepairint,intq; int main() { ios::sync_with_stdio(false); cin.tie(0); memset(dist, -1, sizeof(dist)); int n,m,a,b; cinnmab; for(int i0;ia;i) { int x,y; cinxy; dist[x][y]0; q.push({x,y}); } while(!q.empty()) { auto curq.front(); q.pop(); int xcur.first; int ycur.second; for(int i0;i4;i) { int nxxdx[i]; int nyydy[i]; if(nx1nxnny1nymdist[nx][ny]-1) { dist[nx][ny]dist[x][y]1; q.push({nx,ny}); } } } for(int i0;ib;i) { int x,y; cinxy; coutdist[x][y]\n; } return 0; }P3395 路障完全预判啊我一开始就是这么写的还觉得咋这么简单#includebits/stdc.h using namespace std; const int MAX 1005; int block_time[MAX][MAX]; int dist[MAX][MAX]; int dx[] {-1,1,0,0}; int dy[] {0,0,-1,1}; int n; bool bfs() { memset(dist, -1, sizeof(dist)); queuepairint,int q; q.push({1, 1}); dist[1][1] 0; if(n 1) return true; while(!q.empty()) { auto cur q.front(); q.pop(); int x cur.first; int y cur.second; int t dist[x][y]; if(x n y n) return true; for(int i0;i4;i) { int nx x dx[i]; int ny y dy[i]; int nt t 1; if(nx 1 || nx n || ny 1 || ny n) continue; if(dist[nx][ny] ! -1) continue; if(block_time[nx][ny] 0 || nt block_time[nx][ny])//在路障放之前经过就可以了 { dist[nx][ny] nt; q.push({nx, ny}); } } } return dist[n][n] ! -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin T; while(T--) { memset(block_time, 0, sizeof(block_time)); cin n; int cnt 2 * n - 2; for(int i1;icnt;i) { int x,y; cin x y; block_time[x][y] i; //记录放置路障的时间便于函数里和走路的时间相比较 } if(bfs()) cout Yes\n; else cout No\n; } return 0; }P1379 八数码难题我觉得这个有点动态规划的意思了用了记忆化数组防止重复入队列我总是看到什么就直接读入什么比如看到3*3矩阵就直接想输入二维数组但其实字符串更好操作也不超时感觉以下分析很重要一次移动空格就会产生一个新的棋盘状态。于是可以建立一张隐式图节点一种棋盘布局 边通过一次合法移动可以互相转化的两个布局每次移动代价都是 1要求最少移动次数因此使用 BFS。#includebits/stdc.h using namespace std; int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; const string target 123804765; int bfs(string start) { queuepairstring, int q; unordered_setstring vis; q.push({start, 0}); vis.insert(start); while(!q.empty()) { auto cur q.front(); q.pop(); string s cur.first; int step cur.second; if(s target) { return step; } int pos s.find(0);//记住是字符‘0’ int x pos / 3;//一开始没想到这样来确认他的坐标 int y pos % 3; for(int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if(nx 0 nx 3 ny 0 ny 3) { int np nx * 3 ny; string ns s; swap(ns[pos], ns[np]); if(!vis.count(ns)) { vis.insert(ns);//存入记忆 q.push({ns, step 1}); } } } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); string st; cin st; cout bfs(st) endl; return 0; }END