时间限制：1.0s   内存限制：256.0MB

    

问题描述

　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。

输入格式

　　第一行两个整数n， m，为迷宫的长宽。

　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。

输出格式

　　第一行一个数为需要的最少步数K。

　　第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。

样例输入

Input Sample 1:

3 3

001

100

110

Input Sample 2:

3 3

000

000

000

样例输出

Output Sample 1:

4

RDRD

Output Sample 2:

4

DDRR

数据规模和约定

　　有20%的数据满足：1<=n,m<=10

　　有50%的数据满足：1<=n,m<=50

　　有100%的数据满足：1<=n,m<=500。

迷宫问题可以广搜和深搜：广搜可以求解最短的路径，深搜只是尽快找到一条路径就停止了。

另外深搜用递归的时候，层数一多就不行了，可以用栈来写。广搜可以用队列来存储。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define FOR(i,x,n) for(int i=x;i
            
             =0&&a.x<=N-1&&a.y>=0&&a.y<=M-1&&maze[a.x][a.y]=='0'){ return true; }else{ return false; }}void bfs(){ queue
             
               q; node now; now.x=0;now.y=0; now.steps=0; q.push(now); while(!q.empty()){ node t=q.front();q.pop(); FOR(i,0,4){ node next=t; next.x+=dirX[i];next.y+=dirY[i]; next.steps++; next.path+=dir[i]; if(next.x==N-1&&next.y==M-1){ printf("%d\n",next.steps); //printf("%s",next.path); cout<
              
               <
               
                =0&&next.x<=N-1&&next.y>=0&&next.y<=M-1){ maze[next.x][next.y]=1; } } } } }}int main(){ //freopen("data.txt", "r", stdin); //freopen("data.out", "w", stdout); scanf("%d %d",&N,&M); getchar(); FOR(i,0,N){ FOR(j,0,M){ scanf("%c",&maze[i][j]); } getchar(); } bfs(); //fclose(stdin); //fclose(stdout); return 0;}