第10回ブルーブリッジカップB組テーマ——迷宮

概要
【問題の説明】図は、1が障害であり、0が通行可能な場所である迷路の平面図を示している.010000,000,000,100,001,110,000迷宮の入り口は左上角、出口は右下角で、迷宮の中で、1つの位置からこの上、下、左、右の4つの方向の1つしか歩けません.上の迷路については、入口からDRRURRDDDRの順に迷路を通過することができ、全部で10歩です.このうちD,U,L,Rはそれぞれ下,上,左,右を表す.次のようなより複雑な迷路(30行50列)については、迷路を通過する方法を見つけてください.使用するステップ数が最も少なく、ステップ数が最も少ない前提の下で、辞書の順序が最も小さいものを答えとして見つけてください.ディクショナリシーケンスDでは、コピーされた内容がドキュメントと一致しているかどうかを確認する必要があります.試験問題ディレクトリの下にファイルがあります.txt、内容は以下のテキストと同じです)冬休みにちょうど自分でdfsとbfsを学んだので、ブラシで問題を見たときに見たのは、比較的典型的な問題型でしょう.

//E   -    
#include
#include
#include
using namespace std;
int n,m;
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//    
char d[4]={'U','L','D','R'};//           
struct node//      
{
	int x;int y;//x，y            
	string s;
};
bool in(int x,int y){//       
	return x>0&&x<=n&&y>0&&y<=m;
}
char map[55][55];//  ，       
bool vis[55][55];
void bfs(int x,int y)
{
	queue<node >q;
	node cur,nex;//   ，         ，     
	//cur    ，nex     
	cur.x=x;
	cur.y=y;
	cur.s="";
	q.push(cur);
	while(!q.empty())
	{	
		cur=q.front();
		q.pop();

		for(int i=0;i<4;i++){
			 nex.x=cur.x+dir[i][0];
			 nex.y=cur.y+dir[i][1];
			 if(in(nex.x,nex.y)&&map[nex.x][nex.y]!='1'&&!vis[nex.x][nex.y]){//          ，          
			 	nex.s=cur.s+d[i];//      
			 	vis[nex.x][nex.y]=true;//        
			 	if(nex.x==n&&nex.y==m){//     ，           
			 		cout<<nex.s<<endl;
			 		return;
				 }
				 q.push(nex);//    
			 }
			 
		}
	
		
	}	
	
	
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>map[i][j];
		}
	}
	vis[1][1]=true;//        
	bfs(1,1);//
	
}