走玉米地迷宫，一般有两种简单策略，遇到岔路总是优先沿着自己的左手方向，或者右手方向走。给一个迷宫，给出这两种策略的步数，再给出最短路径的长度。
######### #.#.#.#.# S.......E #.#.#.#.# ######### 迷宫示例
前两种策略用DFS的方法，最后一种用BFS的方法分别确定路线。易错点：
1.这道题目因为在走的时候遇到死路需要回头，且这个步数也要计算在内，所以不需要将走过的路设置标志。
2.总是沿着当前的左边或者右边走，即方向需要不断调整
贴代码如下：
1 #include<iostream> 2 #include<string> 3 #include<queue> 4 using namespace std; 5 typedef class 6 { 7 public: 8 int x,y; 9 int path; 10 }vertex; 11 12 char maze[41][41]; 13 int trace[41][41]; 14 int lpath,rpath,spath; 15 queue<vertex> bfq; 16 17 int incre[4][8]={ //first LEFT, then MID, last RIGHT 18 {-1,0,0,1,1,0,0,-1}, 19 {0,1,1,0,0,-1,-1,0}, 20 {1,0,0,-1,-1,0,0,1}, 21 {0,-1,-1,0,0,1,1,0} 22 }; 23 24 25 int LDFS(int x,int y,int ind) 26 { 27 int nind; 28 trace[x][y]=0; 29 if(maze[x][y]=='E') 30 { 31 cout<<lpath<<" "; 32 return -1; 33 } 34 //左转 35 if(maze[x+incre[ind][0]][y+incre[ind][1]]!='#'&&trace[x+incre[ind][0]][y+incre[ind][1]]==0) 36 { 37 lpath++; 38 nind=(ind+3)%4; 39 if(LDFS(x+incre[ind][0],y+incre[ind][1],nind)==-1) return -1; 40 } 41 //直行 42 if(maze[x+incre[ind][2]][y+incre[ind][3]]!='#'&&trace[x+incre[ind][2]][y+incre[ind][3]]==0) 43 { 44 lpath++; 45 if(LDFS(x+incre[ind][2],y+incre[ind][3],ind)==-1) return -1; 46 } 47 //右转 48 if(maze[x+incre[ind][4]][y+incre[ind][5]]!='#'&&trace[x+incre[ind][4]][y+incre[ind][5]]==0) 49 { 50 lpath++; 51 nind=(ind+1)%4; 52 if(LDFS(x+incre[ind][4],y+incre[ind][5],nind)==-1) return -1; 53 } 54 //后转 55 if(maze[x+incre[ind][6]][y+incre[ind][7]]!='#'&&trace[x+incre[ind][6]][y+incre[ind][7]]==0) 56 { 57 lpath++; 58 nind=(ind+2)%4; 59 if(LDFS(x+incre[ind][6],y+incre[ind][7],nind)==-1) return -1; 60 } 61 62 return lpath; 63 } 64 65 66 67 68 69 int RDFS(int x,int y,int ind) 70 { 71 int nind; 72 trace[x][y]=0; 73 if(maze[x][y]=='E') 74 { 75 cout<<rpath<<" "; 76 return -1; 77 } 78 //右转 79 if(maze[x+incre[ind][4]][y+incre[ind][5]]!='#'&&trace[x+incre[ind][4]][y+incre[ind][5]]==0) 80 { 81 rpath++; 82 nind=(ind+1)%4; 83 if(RDFS(x+incre[ind][4],y+incre[ind][5],nind)==-1) return -1; 84 } 85 if(maze[x+incre[ind][2]][y+incre[ind][3]]!='#'&&trace[x+incre[ind][2]][y+incre[ind][3]]==0) 86 { 87 rpath++; 88 89 if(RDFS(x+incre[ind][2],y+incre[ind][3],ind)==-1) return -1; 90 } 91 if(maze[x+incre[ind][0]][y+incre[ind][1]]!='#'&&trace[x+incre[ind][0]][y+incre[ind][1]]==0) 92 { 93 rpath++; 94 nind=(ind+3)%4; 95 if(RDFS(x+incre[ind][0],y+incre[ind][1],nind)==-1) return -1; 96 } 97 if(maze[x+incre[ind][6]][y+incre[ind][7]]!='#'&&trace[x+incre[ind][6]][y+incre[ind][7]]==0) 98 { 99 rpath++; 100 nind=(ind+2)%4; 101 if(RDFS(x+incre[ind][6],y+incre[ind][7],nind)==-1) return -1; 102 } 103 return rpath; 104 } 105 106 void BFS(vertex v,int ind) 107 { 108 vertex a,b; 109 bfq.push(v); 110 trace[v.x][v.y]=1; 111 while(bfq.size()!=0) 112 { 113 a=bfq.front(); 114 bfq.pop(); 115 if(maze[a.x+incre[ind][4]][a.y+incre[ind][5]]!='#'&&trace[a.x+incre[ind][4]][a.y+incre[ind][5]]==0) 116 { 117 trace[a.x+incre[ind][4]][a.y+incre[ind][5]]=1; 118 b.x=a.x+incre[ind][4]; b.y=a.y+incre[ind][5]; b.path=a.path+1; 119 if(maze[b.x][b.y]=='E') 120 { 121 cout<<b.path<<endl; 122 break; 123 } 124 bfq.push(b); 125 } 126 if(maze[a.x+incre[ind][2]][a.y+incre[ind][3]]!='#'&&trace[a.x+incre[ind][2]][a.y+incre[ind][3]]==0) 127 { 128 trace[a.x+incre[ind][2]][a.y+incre[ind][3]]=1; 129 b.x=a.x+incre[ind][2]; b.y=a.y+incre[ind][3]; b.path=a.path+1; 130 if(maze[b.x][b.y]=='E') 131 { 132 cout<<b.path<<endl; 133 break; 134 } 135 bfq.push(b); 136 } 137 if(maze[a.x+incre[ind][0]][a.y+incre[ind][1]]!='#'&&trace[a.x+incre[ind][0]][a.y+incre[ind][1]]==0) 138 { 139 trace[a.x+incre[ind][0]][a.y+incre[ind][1]]=1; 140 b.x=a.x+incre[ind][0]; b.y=a.y+incre[ind][1]; b.path=a.path+1; 141 if(maze[b.x][b.y]=='E') 142 { 143 cout<<b.path<<endl; 144 break; 145 } 146 bfq.push(b); 147 } 148 if(maze[a.x+incre[ind][6]][a.y+incre[ind][7]]!='#'&&trace[a.x+incre[ind][6]][a.y+incre[ind][7]]==0) 149 { 150 trace[a.x+incre[ind][6]][a.y+incre[ind][7]]=1; 151 b.x=a.x+incre[ind][6]; b.y=a.y+incre[ind][7]; b.path=a.path+1; 152 if(maze[b.x][b.y]=='E') 153 { 154 cout<<b.path<<endl; 155 break; 156 } 157 bfq.push(b); 158 } 159 } 160 } 161 162 163 164 165 166 167 int main() 168 { 169 int instan,w,h,i,j,sx,sy,ind; 170 char in; 171 cin>>instan; 172 for(int Num=0;Num<instan;Num++) 173 { 174 cin>>w>>h; 175 for(i=0;i<h;i++) 176 for(j=0;j<w;j++) 177 { 178 cin>>in; 179 maze[i][j]=in; 180 if(maze[i][j]=='S') 181 { 182 sx=i;sy=j; 183 } 184 } 185 if(sy==0) ind=0; 186 if(sx==0) ind=1; 187 if(sy==(w-1)) ind=2; 188 if(sx==(h-1)) ind=3; 189 lpath=1; 190 memset(trace,0,sizeof(trace)); 191 lpath=LDFS(sx,sy,ind); 192 rpath=1,spath=1; 193 memset(trace,0,sizeof(trace)); 194 rpath=RDFS(sx,sy,ind); 195 //cout<<lpath<<" "<<rpath<<endl; 196 vertex vs; 197 vs.x=sx;vs.y=sy;vs.path=1; 198 memset(trace,0,sizeof(trace)); 199 BFS(vs,ind); 200 while(bfq.empty()!=1) 201 { 202 bfq.pop(); 203 } 204 } 205 return 0; 206 }