bfs求最短路，递归打印最短路的具体路径；

难点：

　　当前状态和转弯方式很复杂，要仔细处理；

　　递归打印：用一个数组存储路径中结点的前一个节点，递归查找 （bfs无法确定下一个结点，但对于没一个结点，它的上一个结点是确定的！）

 

 

ps：输出因为太懒不想处理所以按书上打的；递归打印理解有点麻烦。。。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 using namespace std; 8 9 struct node { 10 int x,y; 11 int w; 12 void init (int nx,int ny,int nw){ 13 x=nx; 14 y=ny; 15 w=nw; 16 } 17 }p[10][10][5]; 18 19 int visit[10][10][5]; 20 int map[10][10][4]; 21 int dir[4][3][2]={ {-1,0,0,-1,0,1}, 22 { 0,1,-1,0,1,0}, 23 { 1,0,0,1,0,-1}, 24 { 0,-1,1,0,-1,0} 25 }; 26 27 int id (char c){ 28 if (c=='N'||c=='F') 29 return 0; 30 else if (c=='E'||c=='L') 31 return 1; 32 else if (c=='S'||c=='R') 33 return 2; 34 else return 3; 35 } 36 node ans[1000]; 37 int tot; 38 int x0,y0,x1,y1,w1,sx,sy; 39 40 void print (int x,int y,int w); 41 42 int bfs (int x,int y,int w){ 43 queue
           
             q; 44 while (!q.empty ()) 45 q.pop (); 46 node a,b; 47 a.init (x,y,w); 48 visit[a.x][a.y][a.w]=0; 49 q.push (a); 50 while (!q.empty ()){ 51 a=q.front ();//cout<
            
             <<" "<
             
              <<" "<
              
               <
               
                9||yy<1||yy>9) 69 continue ; 70 if (visit[xx][yy][ww]>=0) 71 continue ; 72 visit[xx][yy][ww]=visit[a.x][a.y][a.w]+1; 73 p[xx][yy][ww]=a;　　　　//存储路径中的父结点 74 q.push (b); 75 } 76 77 } 78 } 79 return 0; 80 } 81 82 void print (int x,int y,int w){ 83 vector
                
                  v; 84 node a,b; 85 a.init (x,y,w); 86 v.push_back (a); 87 while (visit[a.x][a.y][a.w]){ 88 a=p[a.x][a.y][a.w]; 89 v.push_back (a); 90 } 91 a.init (x0,y0,w1); 92 v.push_back (a); 93 94 int cnt=0; 95 for (int i=v.size()-1;i>=0;i--){ 96 if (cnt%10==0) cout<<" "; 97 cout<<" ("<
                 
                  <<","<
                  
                   <<")"; 98 if (++cnt%10==0) cout<
                   
                    >s){106 if (strcmp (s,"END")==0)107 break ;108 tot=0;109 memset (map,0,sizeof map);110 memset (visit,-1,sizeof visit);111 cout<
                    <
                     
                      >x1>>y1>>c>>sx>>sy;114 x0=x1;y0=y1;115 w1=id (c);116 x1+=dir[w1][0][0];117 y1+=dir[w1][0][1];118 int xx,yy;119 while (cin>>xx&&xx){120 cin>>yy;121 gets (s);122 int i=1;123 int j=id (s[1]);124 while (s[i++]!='*'){ //cout<
                      <<" "<