写了好长(4K),一下就AC了,挺好。思路简单,写着真墨迹。
1 #include <stdio.h> 2 #include <iostream> 3 #include <string> 4 #include <string.h> 5 #define maxn 50 6 using namespace std; 7 int m,n; 8 int sx,sy,ex,ey; 9 int count[maxn][maxn]; 10 bool v[maxn][maxn]; 11 string gird[maxn]; 12 int dir[4][2]={ 13 -1,0,1,0, 14 0,-1,0,1 15 }; 16 void dfs(int x,int y) 17 { 18 int tx,ty; 19 if(x==ex&&y==ey) 20 return ; 21 for(int i=0;i<4;++i) 22 { 23 tx=x+dir[i][0]; 24 ty=y+dir[i][1]; 25 if(tx<n&&tx>=0&&ty<m&&ty>=0&&gird[tx][ty]!='#'&&count[x][y]+1<count[tx][ty]&&v[tx][ty]==0) 26 { 27 v[tx][ty]=1; 28 count[tx][ty]=count[x][y]+1; 29 dfs(tx,ty); 30 v[tx][ty]=0; 31 } 32 } 33 return ; 34 35 } 36 void swap(int &a1,int &b1,int &a2,int &b2) 37 { 38 int t; 39 t=a1;a1=a2;a2=t; 40 t=b1;b1=b2;b2=t; 41 return ; 42 } 43 int judge(int lx,int ly,int nx,int ny) 44 { 45 if(nx-lx==-1&&ny-ly==0 ) return 1; //1表示向上 46 if(nx-lx==1 &&ny-ly==0 ) return 2; //2表示向下 47 if(nx-lx==0 &&ny-ly==1 ) return 3; //3表示向右 48 if(nx-lx==0 &&ny-ly==-1) return 4; //4表示向左 49 } 50 int dfsleft(int x,int y,int lx,int ly) 51 { 52 if(x<0||x>=n||y<0||y>=m||gird[x][y]=='#') 53 return 0; 54 if(x==ex&&y==ey) 55 return 1; 56 if(lx==-1&&ly==-1) //该店为起点的时候 57 { 58 lx=x; 59 ly=y; 60 if(sx==0&&x+1<n) 61 return 1+dfsleft(x+1,y,lx,ly); 62 if(sx==n-1&&x-1>=0) 63 return 1+dfsleft(x-1,y,lx,ly); 64 if(sy==0&&sy+1<m) 65 return 1+dfsleft(x,y+1,lx,ly); 66 if(sy==m-1&&sy-1>=0) 67 return 1+dfsleft(x,y-1,lx,ly); 68 } 69 int sign=judge(lx,ly,x,y); 70 if(sign==1) 71 { 72 if(y-1>=0&&gird[x][y-1]!='#') 73 return 1+dfsleft(x,y-1,x,y); 74 else if(x-1>=0&&gird[x-1][y]!='#') 75 return 1+dfsleft(x-1,y,x,y); 76 else if(y+1<m&&gird[x][y+1]!='#') 77 return 1+dfsleft(x,y+1,x,y); 78 else if(x+1<n&&gird[x+1][y]!='#') 79 return 1+dfsleft(x+1,y,x,y); 80 } 81 if(sign==2) 82 { 83 if(y+1<m&&gird[x][y+1]!='#') 84 return 1+dfsleft(x,y+1,x,y); 85 else if(x+1<n&&gird[x+1][y]!='#') 86 return 1+dfsleft(x+1,y,x,y); 87 else if(y-1>=0&&gird[x][y-1]!='#') 88 return 1+dfsleft(x,y-1,x,y); 89 else if(x-1>=0&&gird[x-1][y]!='#') 90 return 1+dfsleft(x-1,y,x,y); 91 } 92 if(sign==3) 93 { 94 if(x-1>=0&&gird[x-1][y]!='#') 95 return 1+dfsleft(x-1,y,x,y); 96 else if(y+1<m&&gird[x][y+1]!='#') 97 return 1+dfsleft(x,y+1,x,y); 98 else if(x+1<n&&gird[x+1][y]!='#') 99 return 1+dfsleft(x+1,y,x,y); 100 else if(y-1>=0&&gird[x][y-1]!='#') 101 return 1+dfsleft(x,y-1,x,y); 102 } 103 if(sign==4) 104 { 105 106 if(x+1<n&&gird[x+1][y]!='#') 107 return 1+dfsleft(x+1,y,x,y); 108 else if(y-1>=0&&gird[x][y-1]!='#') 109 return 1+dfsleft(x,y-1,x,y); 110 else if(x-1>=0&&gird[x-1][y]!='#') 111 return 1+dfsleft(x-1,y,x,y); 112 else if(y+1<m&&gird[x][y+1]!='#') 113 return 1+dfsleft(x,y+1,x,y); 114 } 115 //四个方向都整完了。 116 } 117 int main() 118 { 119 int t,i,j,k; 120 while(cin>>t) 121 { 122 while(t--) 123 { 124 cin>>m>>n; 125 for(i=0;i<n;++i) 126 { 127 cin>>gird[i]; 128 for(j=0;j<m;++j) 129 { 130 if(gird[i][j]=='S') 131 { 132 sx=i; 133 sy=j; 134 } 135 if(gird[i][j]=='E') 136 { 137 ex=i; 138 ey=j; 139 } 140 } 141 } 142 cout<<dfsleft(sx,sy,-1,-1)<<" "; 143 swap(sx,sy,ex,ey); 144 cout<<dfsleft(sx,sy,-1,-1)<<" "; 145 swap(sx,sy,ex,ey); 146 memset(v,0,sizeof(v)); 147 for(j=0;j<n;++j) 148 for(k=0;k<m;++k) 149 count[j][k]=10000000; 150 count[sx][sy]=1; 151 v[sx][sy]=1; 152 dfs(sx,sy); 153 cout<<count[ex][ey]<<endl; 154 } 155 } 156 return 0; 157 }