题解 | 迷宫问题

#include<bits/stdc++.h>
using namespace std;
class Pos{
	public:
		int px;
		int py;
		Pos* fa;
		Pos(int px,int py,Pos *father):px(px),py(py),fa(fa){
		}
}; 

const int N=110;

int h,w,g[N][N];
bool vis[N][N];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

void print_road(Pos *t){
	if(t->fa!=NULL){
		print_road(t->fa);
		cout<<"("<<t->px<<","<<t->py<<")"<<endl;
	}
}

void bfs(int sx,int sy){
	
	vis[sx][sy]=true;
	queue<Pos *> q;
	Pos *ps=new Pos(sx,sy,NULL),*tp,*temp;
	ps->px=sx;ps->py=sy;ps->fa=NULL;
	q.push(ps);
		
	int x,y,tx,ty;
	while(!q.empty()){
		
		temp=q.front();q.pop();
		x=temp->px;y=temp->py;
		
		for(int i=0;i<4;i++){
			tx=x+dx[i];
			ty=y+dy[i];
			if(tx>=0&&tx<=h-1&&ty>=0&&ty<=w-1&&!vis[tx][ty]&&g[tx][ty]==0){
				vis[tx][ty]=true;
				tp=new Pos(tx,ty,NULL);
//				cout<<tx<<" "<<ty<<endl;
				tp->fa=temp;
				q.push(tp);
				if(tx==h-1&&ty==w-1){
					cout<<"("<<0<<","<<0<<")"<<endl;
					print_road(tp);
					return;
				}
				
			}
		}
		
		
	}
	
	
}


void solve(){
	
	bfs(0,0);
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>h>>w;
	
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>g[i][j];
		}
	}
	
	solve();
	

    return 0;
}