---恢复内容开始---
http://poj.org/problem?id=3083
题目大意就是给你要你从S走到E，且只有.代表的地方才是可以走的，有三种方式的走法。
一、是向左优先转，从S到E的步数。
二、是向右优先转，从S到E的步数。
三、S到E的最短路径，小于等于前面二者。
思路：这题比较难的就是怎么确定方向，对于向左走的人。它的右边对于我们来说是向上的，解决这个办法可以用数字来模拟方向
| 0 | ||
| 1 | 当前位置 | 3 |
| 2 |
当你的是从3走到当前位置时，对于你来说，你的左边就是2，右边就是0，
而当你的优先偏转方向是#也就是不能走时，你应该按原方向走，意思就是对于左优先你走的顺序应该2 1 0 3
右优先就是0 1 2 3 而不是0 3 2 1
我的代码也是借鉴了别人的，比较繁琐，但是思路比较清晰，个人觉得比较好理解
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <queue> 5 6 using namespace std; 7 8 queue<int >first; //定义两个队列，用来分别存位置当前位置，当然也可以用pair类型，那样定义一个就可以了 9 queue<int >second; 10 char str[50][50]; 11 int lstep,rstep,bstep[50][50]; 12 bool mark[50][50]; //用来标记走过的，在前两个搜索时不需要用，因为有可能会走原路，用在第三个求最短路径 13 int lbfs(int i,int j,int d) //向左优先转 14 { 15 lstep++; 16 if(str[i][j]=='E') return 0; 17 switch(d) 18 { 19 case 0: 20 { 21 if(str[i][j-1]=='.'||str[i][j-1]=='E') //记得要加==‘E’，不然它是永远也找不到E的 22 lbfs(i,j-1,1); 23 else if(str[i-1][j]=='.'||str[i-1][j]=='E') 24 lbfs(i-1,j,0); 25 else if(str[i][j+1]=='.'||str[i][j+1]=='E') 26 lbfs(i,j+1,3); 27 else if(str[i+1][j]=='.'||str[i+1][j]=='E') 28 lbfs(i+1,j,2); 29 break; 30 } 31 case 1: 32 { 33 if(str[i+1][j]=='.'||str[i+1][j]=='E') 34 lbfs(i+1,j,2); 35 else if(str[i][j-1]=='.'||str[i][j-1]=='E') 36 lbfs(i,j-1,1); 37 else if(str[i-1][j]=='.'||str[i-1][j]=='E') 38 lbfs(i-1,j,0); 39 else if(str[i][j+1]=='.'||str[i][j+1]=='E') 40 lbfs(i,j+1,3); 41 break; 42 } 43 case 2: 44 { 45 if(str[i][j+1]=='.'||str[i][j+1]=='E') 46 lbfs(i,j+1,3); 47 else if(str[i+1][j]=='.'||str[i+1][j]=='E') 48 lbfs(i+1,j,2); 49 else if(str[i][j-1]=='.'||str[i][j-1]=='E') 50 lbfs(i,j-1,1); 51 else if(str[i-1][j]=='.'||str[i-1][j]=='E') 52 lbfs(i-1,j,0); 53 break; 54 } 55 case 3: 56 { 57 if(str[i-1][j]=='.'||str[i-1][j]=='E') 58 lbfs(i-1,j,0); 59 else if(str[i][j+1]=='.'||str[i][j+1]=='E') 60 lbfs(i,j+1,3); 61 else if(str[i+1][j]=='.'||str[i+1][j]=='E') 62 lbfs(i+1,j,2); 63 else if(str[i][j-1]=='.'||str[i][j-1]=='E') 64 lbfs(i,j-1,1); 65 break; 66 } 67 } 68 return 0; 69 } 70 int rbfs(int i,int j,int d) 71 { 72 rstep++; 73 if(str[i][j]=='E') return 0; 74 switch(d) 75 { 76 case 0: 77 { 78 if(str[i][j+1]=='.'||str[i][j+1]=='E') 79 rbfs(i,j+1,3); 80 else if(str[i-1][j]=='.'||str[i-1][j]=='E') 81 rbfs(i-1,j,0); 82 else if(str[i][j-1]=='.'||str[i][j-1]=='E') 83 rbfs(i,j-1,1); 84 else if(str[i+1][j]=='.'||str[i+1][j]=='E') 85 rbfs(i+1,j,2); 86 break; 87 } 88 case 1: 89 { 90 if(str[i-1][j]=='.'||str[i-1][j]=='E') 91 rbfs(i-1,j,0); 92 else if(str[i][j-1]=='.'||str[i][j-1]=='E') 93 rbfs(i,j-1,1); 94 else if(str[i+1][j]=='.'||str[i+1][j]=='E') 95 rbfs(i+1,j,2); 96 else if(str[i][j+1]=='.'||str[i][j+1]=='E') 97 rbfs(i,j+1,3); 98 break; 99 } 100 case 2: 101 { 102 if(str[i][j-1]=='.'||str[i][j-1]=='E') 103 rbfs(i,j-1,1); 104 else if(str[i+1][j]=='.'||str[i+1][j]=='E') 105 rbfs(i+1,j,2); 106 else if(str[i][j+1]=='.'||str[i][j+1]=='E') 107 rbfs(i,j+1,3); 108 else if(str[i-1][j]=='.'||str[i-1][j]=='E') 109 rbfs(i-1,j,0); 110 break; 111 } 112 case 3: 113 { 114 if(str[i+1][j]=='.'||str[i+1][j]=='E') 115 rbfs(i+1,j,2); 116 else if(str[i][j+1]=='.'||str[i][j+1]=='E') 117 rbfs(i,j+1,3); 118 else if(str[i-1][j]=='.'||str[i-1][j]=='E') 119 rbfs(i-1,j,0); 120 else if(str[i][j-1]=='.'||str[i][j-1]=='E') 121 rbfs(i,j-1,1); 122 break; 123 } 124 } 125 return 0; 126 } 127 int dfs(int i,int j) 128 { 129 memset(mark,false,sizeof(mark)); //切记对这些数值都要进行清零，还有对队列要记得清空，不然很容易出问题 130 memset(bstep,0,sizeof(bstep)); 131 bstep[i][j]=1; 132 while(!first.empty()) 133 { 134 first.pop(); 135 second.pop(); 136 } 137 int he,ba; 138 first.push(i); 139 second.push(j); 140 mark[i][j]=true; 141 while(!first.empty()) 142 { 143 he=first.front(); 144 first.pop(); 145 ba=second.front(); 146 second.pop(); 147 if(str[he][ba]=='E') 148 { 149 printf(" %d ",bstep[he][ba]); 150 break; 151 } 152 if((str[he+1][ba]=='.'||str[he+1][ba]=='E')&&!mark[he+1][ba]) //对于没走过的路又可以走的路进行标记，这样可以确定这个路是最短的。 153 { 154 first.push(he+1); 155 second.push(ba); 156 mark[he+1][ba]=true; 157 bstep[he+1][ba]=bstep[he][ba]+1; 158 } 159 if((str[he][ba+1]=='.'||str[he][ba+1]=='E')&&!mark[he][ba+1]) 160 { 161 first.push(he); 162 second.push(ba+1); 163 mark[he][ba+1]=true; 164 bstep[he][ba+1]=bstep[he][ba]+1; 165 } 166 if((str[he][ba-1]=='.'||str[he][ba-1]=='E')&&!mark[he][ba-1]) 167 { 168 first.push(he); 169 second.push(ba-1); 170 mark[he][ba-1]=true; 171 bstep[he][ba-1]=bstep[he][ba]+1; 172 } 173 if((str[he-1][ba]=='.'||str[he-1][ba]=='E')&&!mark[he-1][ba]) 174 { 175 first.push(he-1); 176 second.push(ba); 177 mark[he-1][ba]=true; 178 bstep[he-1][ba]=bstep[he][ba]+1; 179 } 180 } 181 return 0; 182 } 183 int main() 184 { 185 int n,m,t,i,j,k,start; 186 scanf("%d",&t); 187 while(t) 188 { 189 t--; 190 memset(str,0,sizeof(str)); 191 lstep=1; 192 rstep=1; 193 scanf("%d%d",&m,&n); 194 for(i=1;i<=n;i++) 195 scanf("%s",str[i]); 196 for(i=1,k=0;i<=n;i++) 197 { 198 for(j=0;j<m;j++) 199 if(str[i][j]=='S') 200 { 201 k=1; 202 break; 203 } 204 if(k==1) break; 205 } 206 bstep[i][j]=1; 207 if(i==n) start=0; 208 else if(j==m-1) start=1; 209 else if(i==1) start=2; 210 else start=3; 211 switch(start) 212 { 213 case 0:{ lbfs(i-1,j,0);break;} 214 215 case 1:{ lbfs(i,j-1,1);break;} 216 217 case 2:{ lbfs(i+1,j,2);break;} 218 219 case 3:{ lbfs(i,j+1,3);break;} 220 } 221 switch(start) 222 { 223 case 0:{ rbfs(i-1,j,0);break;} 224 225 case 1:{ rbfs(i,j-1,1);break;} 226 227 case 2:{ rbfs(i+1,j,2);break;} 228 229 case 3:{ rbfs(i,j+1,3);break;} 230 } 231 printf("%d %d",lstep,rstep); 232 dfs(i,j); 233 } 234 return 0; 235 }