题解 | 迷宫问题

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int h,w;
int ch[102][102];
bool vis[102][102]={false};
PII pre[102][102];
int main()
{
  cin>>h>>w;
  for(int i=0;i<h;i++)
  {
    for(int j=0;j<w;j++)
    {
        cin>>ch[i][j];
    }
  }

  queue<PII>q;
  q.push({0,0});
  vis[0][0]=true;
  while(!q.empty())
  {
    auto p=q.front();
    q.pop();
    int x=p.first;
    int y=p.second;

    int dx[]={1,-1,0,0};
    int dy[]={0,0,1,-1};
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=0&&nx<h&&ny>=0&&ny<w)
        {
            if(ch[nx][ny]==0&&vis[nx][ny]==false)
            {
                vis[nx][ny]=true;
                pre[nx][ny]=make_pair(x,y);
                q.push({nx,ny});
            }
        }
    }
  }
  stack<PII>path;
  int x=h-1,y=w-1;
  while(!(x==0&&y==0))
  {
    path.push({x,y});
    auto p=pre[x][y];
    x=p.first;
    y=p.second;
  }
  path.push({0,0});
   
   while(!path.empty())
   {
    auto a=path.top();
    path.pop();
    cout<<"("<<a.first<<","<<a.second<<")"<<endl;
   }
}