2 条题解
-
0
注意!!
狡猾的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真好玩!!
信息
- ID
- 5804
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 2
- 标签
- 递交数
- 20
- 已通过
- 7
- 上传者