O1483 【提高】走出迷宫的最短路径

#include<bits/stdc++.h>
using namespace std;
int n,m,a[151][151],sx,sy,zx,zy;
int dx[]{0,1,-1,0,0};
int dy[]{0,0,0,1,-1};
char k[5]{' ','R','L','D','U'};
char pre[151][151];
struct node{
	int x,y,cnt;
};
bool check(int x,int y){
	if(x < 1 || y < 1 || x > n || y > m)return false;
	if(a[x][y] == 1)return false;
	return true;
}
void print(int x,int y){
	if(x == sx && y == sy)return;
	if(pre[x][y]=='R')print(x-1,y);
	if(pre[x][y]=='L')print(x+1,y);
	if(pre[x][y]=='D')print(x,y-1);
	if(pre[x][y]=='U')print(x,y+1);
	if(x == zx && y == zy)cout << "(" << x <<","<< y <<")";
	else cout << "(" << x <<","<< y <<")->";
}
void bfs(){
	queue<node> q;
	q.push((node){sx,sy,0});
	a[sx][sy]=1;
	while(!q.empty()){
		node t= q.front();
		int nx=t.x;
		int ny=t.y;
		q.pop();
		if(nx == zx && ny == zy){
			cout << "("<<sx<<","<<sy<<")->";
			print(zx,zy);
			return;
		}
		for(int i = 1;i <= 4;i++){
			int X=nx+dx[i];
			int Y=ny+dy[i];
			if(check(X,Y)){
				a[X][Y]=1;
				pre[X][Y]=k[i];
				q.push((node){X,Y,t.cnt+1});
			}
		}
	}
	cout <<"no way";
}
int main(){
	cin >>n >> m;
	for(int i= 1;i <= n;i++)for(int j = 1;j <= m;j++)cin >> a[i][j];
	cin >> sx >> sy >> zx >> zy; 
	bfs();
	return 0;
}