a_bad_seed @ 2023-01-13 15:19:24
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
struct node
{
int x, y;
int step;
} a, b;
int n;
char c[1010][1010];
int maze[1010][1010];
bool vis[1010][1010];
int dir[4][4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int x_1, y_1, x_2, y_2;
queue<node> q;
bool in(int x, int y)
{
return 0 <= x && x < n && 0 <= y && y < n;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
std::ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> c[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
maze[i][j] = c[i][j] - '0';
}
}
cin >> x_1 >> y_1 >> x_2 >> y_2;
x_1--, y_1--, x_2--, y_2--;
if (x_1 == x_2 && y_1 == y_2)
{
cout << 0;
return 0;
}
q.push((node){x_1, y_1, 0});
vis[x_1][y_1] = 1;
while (!q.empty())
{
a = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int dx = a.x + dir[i][0];
int dy = a.y + dir[i][1];
if (!vis[dx][dy] && !maze[dx][dy] && in(dx, dy))
{
b.x = dx;
b.y = dy;
b.step = a.step + 1;
if (dx == x_2 && dy == y_2)
{
cout << b.step;
return 0;
}
q.push(b);
}
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
by Fractured_Angel @ 2023-01-13 15:39:20
目测bfs里根本没标记vis?
by a_bad_seed @ 2023-01-13 15:39:56
啊对对对
by a_bad_seed @ 2023-01-13 15:40:06
解决了