`#include [HTML_REMOVED]//空间超出
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
typedef pair[HTML_REMOVED] PII;
const int N = 1010;
int dx[4] = { 0,0,-1,1 }, dy[4] = { 1,-1,0,0 };//上下左右
int n;
int g[N][N],
bool d[N][N];
PII ds[N][N];
void bfs()
{
queue[HTML_REMOVED] q;
d[1][1] = 1;
ds[1][1] = { -1,-1 };//都指向前面的位置
q.push({ 1, 1 });
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i)
{
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 1 && x <= n && y >= 1 && y <= n && g[x][y] == 0 && d[x][y] == 0)
{
ds[x][y] = { t.first,t.second };
d[x][y] = 1;//怎么样保证d[n][n]不会被后面的路径所更新呢,因为改点访问过了d[x][y] == 0就不成立了
q.push({ x, y });//记录路径的话就将,该点指向其父节点,从尾结点开始即可得到路径
}
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i)
for (int j = 1; j <= n; j++)
cin >> g[i][j];
bfs();
PII e = {n,n};
PII flag = { -1,-1 };
stack[HTML_REMOVED] s;
while (e!=flag)
{
s.push(e);
e = ds[e.first][e.second];
}
while (s.size())
{
cout << s.top().first -1<< ” ” << s.top().second -1<< endl;
s.pop();
}
return 0;
}
`