2 条题解
-
2
#include<bits/stdc++.h> using namespace std; const int N=1e3+5; char a[N][N]; int vis[N][N]; int n,m,sx,sy,fx,fy; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; struct point{ int x,y; }; queue <point> q; int bfs(int x,int y){ point p={x,y}; q.push(p); while(!q.empty()){ point temp=q.front(); q.pop(); if(temp.x==fx && temp.y==fy) return vis[temp.x][temp.y]-1; else{ for(int i=0;i<4;i++){ point np=temp; np.x+=dx[i]; np.y+=dy[i]; if(np.x>=1 && np.x<=n && np.y>=1 && np.y<=n && a[np.x][np.y]=='0' && vis[np.x][np.y]==0){ q.push(np); vis[np.x][np.y]=vis[temp.x][temp.y]+1; } } } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } cin>>sx>>sy>>fx>>fy; vis[sx][sy]=1; cout<<bfs(sx,sy)<<endl; return 0; }
-
1
注意!!
狡猾的y1函数会伪装成变量诱导你
实在可恶!!!
#include <bits/stdc++.h> using namespace std; int n; char a[1007][1007]; int x1, y11, x2, y2; struct node { int x; int y; int steps; }; int xo[4] = {1, 0, 0, -1}; //x方向 int yo[4] = {0, -1, 1, 0}; //y方向 queue<node> op; int minstep = 99999999; //初始化为一个很大的值 //BFS void bfs(int x1, int y1) { //检查起点和终点是否是障碍物 if (a[x1][y11] == '1' || a[x2][y2] == '1') { minstep = -1; //是障碍,无法到达 return; } op.push(node{x1, y11, 0}); a[x1][y1] = '1'; // 标记起点为已访问 while (!op.empty()) { node tou = op.front(); op.pop(); if (tou.x == x2 && tou.y == y2) { minstep = tou.steps; return; // 找到目标点,提前返回 } // 遍历四个方向 for (int i = 0; i < 4; i++) { int xx = tou.x + xo[i]; int yy = tou.y + yo[i]; // 检查越界和是否访问过 if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] == '0') { a[xx][yy] = '1'; // 标记该位置为已访问 op.push(node{xx, yy, tou.steps + 1}); } } } } int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } cin >> x1 >> y11 >> x2 >> y2; x1--; y11--; x2--; y2--; // 坐标从1开始,转换为从0开始的索引 bfs(x1, y11); // 如果 minstep 仍是初始值,表示没有找到路径 if (minstep == 99999999) { cout << "-1" << endl; // 无法到达目标(好像有点多余,题里头没要求) } else { cout << minstep; // 输出最短路径的步数 } return 0; } //bfs真好玩!!
- 1
信息
- ID
- 5804
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 2
- 标签
- 递交数
- 20
- 已通过
- 7
- 上传者