这里我使用了一个数组去存每个点是从哪一个点转移过来的。
这样做的一个问题是,要找到一条完整的路径要从终点倒推回去,所有得到的路径是反的。
所有我们可以把终点当做起点,把起点当做终点,最后从起点倒推回去,得到的路径就是正的了。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
using PII = pair<int, int>;
const int N = 1e3 + 10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
int g[N][N];
bool st[N][N];
PII path[N][N];
void bfs()
{
queue<PII> q;
memset(path, -1, sizeof path);
q.push({n - 1, n - 1});
st[n - 1][n - 1] = true;
while (!q.empty())
{
auto t = q.front(); q.pop();
if (t.first == 0 && t.second == 0)
{
printf("0 0\n");
auto pre = path[0][0];
while (pre.first != -1 || pre.second != -1)
{
printf("%d %d\n", pre.first, pre.second);
pre = path[pre.first][pre.second];
}
return;
}
for (int i = 0; i < 4; ++i)
{
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < n && !st[x][y] && g[x][y] == 0)
q.push({x, y}), st[x][y] = true, path[x][y] = t;
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
scanf("%d", &g[i][j]);
bfs();
return 0;
}