正求最短距离->逆推具体路径
注意起点是1还是0,debug半个小时。。。
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int>PII;
int n;
const int N = 1010;
int g[N][N];
bool st[N][N];
PII pre[N][N];
int res = 0;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
void bfs()
{
queue<PII>q;
q.push({ 0,0 });
st[0][0] = true;
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int a = dx[i] + t.x;
int b = dy[i] + t.y;
if (a < 0 || a >= n || b < 0 || b >= n || st[a][b] || g[a][b] == 1)continue;
st[a][b] = true;
pre[a][b] = t;
q.push({ a,b });
}
}
PII start = { 0,0 }, end = { n - 1,n - 1 };
stack<PII>stk;
while (start != end)
{
stk.push(end);
end = pre[end.x][end.y];
}
stk.push(start);
while (stk.size())
{
cout << stk.top().x << ' ' << stk.top().y << endl;
stk.pop();
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> g[i][j];
bfs();
return 0;
}