广度优先搜索

(BFS) $O(n^2)$

深度优先搜索超时

从 (n - 1, n - 1) - > (0, 0) 进行广度优先搜索，用数组存储当前节点是从哪个节点过来的

例如：$ (9,9) -> (8,8) $
- $path[8][8] = (9,9)$

输出是从 (0,0) 开始输出，下一个输出数据在 path[0][0] 中

时间复杂度$O(n^2)$

C++ 代码

#include <iostream>
#include <queue>
using namespace std;

typedef pair<int,int> PII;
const int N = 1001;
int n;

int m[N][N];
PII path[N][N];

const int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};

void bfs() {
    queue<PII> q;
    q.push(make_pair(n - 1,n - 1));
    m[n - 1][n - 1] = 1;
    while (q.size()) {
        auto cur = q.front(); q.pop();
        for (int i = 0; i < 4; i ++ ) {
            int nx = cur.first + dx[i], ny = cur.second + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || m[nx][ny] == 1) continue;
            path[nx][ny] = cur;
            q.push(make_pair(nx,ny));
            m[nx][ny] = 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ ) 
            cin >> m[i][j];

    bfs();
    int i = 0, j = 0;
    while (i != n - 1 || j != n - 1) {
        cout << i << ' ' << j << endl;
        int x, y;
        x = path[i][j].first;
        y = path[i][j].second;
        i = x;
        j = y;
    }
    cout << n - 1 << ' ' << n - 1 << endl;
    return 0;
}