题目描述

https://www.acwing.com/problem/content/1078/

样例

输入样例：
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010;
int n;
int dist[N][N];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int g[N][N];
pair<int, int> pre[N][N];//记录路径
void bfs()
{
    queue<pair<int, int>> q;
    q.push({n - 1, n - 1});
    dist[n - 1][n - 1] = 0;
    pre[n - 1][n - 1] = {0, 0};
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= n) continue;
            if (g[a][b] == 1) continue;
            if (dist[a][b] != -1) continue;
            q.push({a, b});
            dist[a][b] = dist[t.first][t.second] + 1;
            pre[a][b] = 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]);
    memset(dist, -1, sizeof(dist));
    bfs();
    pair<int, int> end(0, 0);
    int x = n - 1, y = n - 1;
    while (true)
    {
        printf("%d %d\n", end.first, end.second);
        if (end.first == n - 1 && end.second == n - 1) break;
        end = pre[end.first][end.second];
    }
    return 0;
}