玄二关
by xXyhhyhhXX @ 2024-06-29 11:42:18
@[xXyhhyhhXX](/user/742071)
```cpp
#include <iostream>
#include <queue>
using namespace std;
struct Point {
int x, y, step;
};
int s[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
Point tPoint(int x, int y, int step) {
Point a;
a.x = x;
a.y = y;
a.step = step;
return a;
}
queue<Point> list;
bool map[1005][1005];
int x1, y1, x2, y2, n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char c;
cin >> c;
if (c == '0') {
map[i][j] = 1;
}
}
}
cin >> x1 >> y1 >> x2 >> y2;
list.push(tPoint(x1 - 1, y1 - 1, 0));
while (!list.empty()) {
Point t = list.front();
list.pop();
// map[t.x][t.y]=0;
//cout<<t.x<<" "<<t.y<<" "<<t.step<<endl;
if ((t.x == x2 - 1) && (t.y == y2 - 1)) {
cout << t.step << endl;
return 0;
}
for (int i = 0; i < 4; i++) {
int px = t.x + s[i][0], py = t.y + s[i][1];
if ((px < n && px >= 0 && py < n && py >= 0) && map[px][py]) {//用&&
list.push(tPoint(px, py, t.step + 1));
map[px][py] = 0;//在这就改成0
}
}
//cout<<list.size()<<endl;
}
return 0;
}
```
by wangzhongqian @ 2024-06-29 12:28:06
@[xXyhhyhhXX](/user/742071)
加个 `vis[1024][1024]` 判断走没走过，走过的节点就不走了。
by yx666 @ 2024-06-29 12:42:19
@[wangzhongqian](/user/1298242) thx,已关
by xXyhhyhhXX @ 2024-06-29 19:48:13
@[yx666](/user/825020) thx,已关
by xXyhhyhhXX @ 2024-06-29 19:48:31