这道题就是个很简单的bfs,每走一步就记录前的点,输出路径的话,我是最后一个点开始依次把前面的结点压入到栈中再弹出来就是从开始到结束的路径了。
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int g[N][N];
bool vis[N][N];
PII pre[N][N];
int n;
void bfs()
{
queue<PII> q;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
pre[0][0] = { -1, -1 };
q.push({ 0, 0 });
vis[0][0] = true;
while (q.size())
{
PII k = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int x = k.first + dx[i], y = k.second + dy[i];
if(x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 0 && !vis[x][y])
{
vis[x][y] = true;
q.push({ x, y });
pre[x][y] = { k.first, k.second};
}
}
}
}
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模板
bfs();
stack<PII> s;
s.push({ n - 1, n - 1 });
PII t = pre[n - 1][n - 1];
// (0, 0)点的前驱结点设为(-1, -1) 依次压栈
while(t.first != -1 && t.second != -1)
{
s.push({ t.first, t.second });
t = pre[t.first][t.second];
}
// 从(0, 0) 出栈
while(s.size())
{
PII k = s.top();
printf("%d %d\n", k.first, k.second);
s.pop();
}
return 0;
}
好!