迷宫问题

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

注意记录状态的唯一性

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 1050;
int g[N][N];
bool st[N][N];
pii pre[N][N];
pii ne[N][N];
int n;
int dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };

void bfs(int sx, int sy)
{
    queue<pii> q;
    q.push({ sx, sy });
    st[sx][sy] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        if (t.x == n && t.y == n) return;
        for (int i = 0; i < 4; i++)
        {
            int nx = t.x + dx[i], ny = t.y + dy[i];
            if (nx<1 || nx>n || ny<1 || ny>n || st[nx][ny] == true) continue;
            if (g[nx][ny] == 1) continue;
            q.push({ nx, ny });
            st[nx][ny] = true;
            pre[nx][ny] = { t.x, t.y };
            //ne[t.x][t.y] = { nx, ny }; 
            //这儿不能这么写，因为如果你用t.x,t.y也就是扩展之前的那个点的话，
            //无法唯一表示这个状态，他会再循环里面更新多次，一般在bfs记录状态的时候，
            //都是些nx,ny，也就是扩展之后的那个点，而且也因为每个点只能遍历一次。
        }
    }
}

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

    bfs(1,1);


    vector<pii> res;

    res.push_back({ n , n });

    pii end = { n,n};
    while (1)
    {
        res.push_back(pre[end.x][end.y]);
        if (pre[end.x][end.y].x == 1 && pre[end.x][end.y].y == 1) break;
        end = pre[end.x][end.y];
    }

    for (int i = res.size() - 1; i >= 0; i--)
    {
        cout << res[i].x-1<< " " << res[i].y-1<< endl;
    }
    return 0;
}