#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 1010;
PII pre[N][N];
int g[N][N];
bool st[N][N];
int n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(int x, int y)
{
    queue<PII> q;
    q.push({x, y});
    st[x][y] = true;

    while(!q.empty())
    {
        PII start = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++)
        {
            int a = start.first + dx[i], b = start.second + dy[i];
            // if(a < 0 || a >= n || b < 0 || b >= n || st[a][b] || g[a][b] == 1) continue;
             if(a >= 0 && a < n && b >= 0 && b < n && g[a][b] == 0 && st[a][b] == false)
             {
                st[a][b] =  true;
                q.push({a, b});
                pre[a][b] = start;
             }

        }

    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    for(int j = 0; j < n; j ++)
    cin >> g[i][j];

    bfs(n - 1, n - 1);

    int x = 0, y = 0;

    while(x != n - 1 || y != n - 1)
    {
        cout << x << " " << y << endl; 
        x = pre[x][y].first, y = pre[x][y].second;
    }
   cout << n - 1 << ' ' << n - 1 << endl;
    return 0;
}

#include <iostream>
#include <string>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int ,int> PII;

const int N = 1000;

PII pre[N][N];//存储当前位置的前驱
int g[N][N];
bool st[N][N];//表示当前位置的状态，若已用则为true,反之为false.
int n;
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};//当前位置的上、下、左、右偏移量

//从(n - 1, n - 1)向(0, 0)搜寻    ----- 便于方案的打印(可理解为前者元素为后续元素的前驱)
void bfs(){
    queue <PII> q;
    q.push({n - 1, n - 1});
    st[n - 1][n - 1] = true;

    while(q.size()){
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++){
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 0 && st[x][y] == false){
                st[x][y] = true;
                q.push({x, y});
                pre[x][y] = t;//存储一下当前合理位置的前驱,即该位置由哪个位置引入
            }
        }
    }

    //打印方案 
    int x = 0, y = 0;
    while(x != n - 1 || y != n - 1){//当x = y = n - 1时,循环截止,因为下标n - 1为第一个元素，它没有前驱
        cout << x << ' ' << y << endl;
        auto t = pre[x][y];
        x = t.x, y = t.y;
    }
    cout << n - 1 << ' ' << n - 1 << endl;//单独打印第一个元素的下标

}

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;
}

为什模第一个就超时，第二个不会，几乎一模一样