题目来源：http://poj.org/problem?id=3009
一道深搜题目，与一般搜索不同的是，目标得一直往一个方向走，直到出界或者遇到阻碍才换方向。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #define inf 0x7fffffff 9 using namespace std; 10 int w,h; 11 int an[4][2]={-1,0, 1,0 ,0,-1, 0,1 }; 12 int bn[25][25],vis[25][25]; 13 int sx,sy,gx,gy; 14 int ans; 15 void dfs(int x,int y,int time) 16 { 17 if (time>=10) return ; 18 if (x<0 || x>=h || y<0 || y>=w) return ; 19 int ok=0; 20 int j=x,k=y; 21 int i; 22 for (i=j-1 ;i>=0 ;i--) 23 { 24 if (bn[i][k]==1) break; 25 if (bn[i][k]==3) {ans=min(ans,time+1) ;return ; } 26 } 27 if (i>=0 && i+1!=x) 28 { 29 bn[i][k]=0; 30 dfs(i+1,k,time+1); 31 bn[i][k]=1; 32 } 33 j=x ;k=y ; 34 for (i=j+1 ;i<h ;i++) 35 { 36 if (bn[i][k]==1) break; 37 if (bn[i][k]==3) {ans=min(ans,time+1) ;return ; } 38 } 39 if (i<h && i-1!=x) 40 { 41 bn[i][k]=0; 42 dfs(i-1,k,time+1); 43 bn[i][k]=1; 44 } 45 j=x ;k=y ; 46 for (i=y-1 ;i>=0 ;i--) 47 { 48 if (bn[j][i]==1) break; 49 if (bn[j][i]==3) {ans=min(ans,time+1) ;return ; } 50 } 51 if (i>=0 && i+1!=y) 52 { 53 bn[j][i]=0; 54 dfs(j,i+1,time+1); 55 bn[j][i]=1; 56 } 57 j=x ;k=y ; 58 for (i=y+1 ;i<w ;i++) 59 { 60 if (bn[j][i]==1) break; 61 if (bn[j][i]==3) {ans=min(ans,time+1) ;return ; } 62 } 63 if (i<w && i-1!=y) 64 { 65 bn[j][i]=0 ; 66 dfs(j,i-1,time+1); 67 bn[j][i]=1; 68 } 69 } 70 int main() 71 { 72 while (cin>>w>>h) 73 { 74 if (!w && !h) break; 75 for (int i=0 ;i<h ;i++) 76 { 77 for (int j=0 ;j<w ;j++) 78 { 79 scanf("%d",&bn[i][j]); 80 if (bn[i][j]==2) {sx=i ;sy=j ; } 81 if (bn[i][j]==3) {gx=i ;gy=j ; } 82 } 83 } 84 int ok=1; 85 if (sx>0 && bn[sx-1][sy]!=1) ok=0; 86 if (sx<h-1 && bn[sx+1][sy]!=1) ok=0; 87 if (sy>0 && bn[sx][sy-1]!=1) ok=0; 88 if (sy<w-1 && bn[sx][sy+1]!=1) ok=0; 89 if (ok) {cout<<-1<<endl;continue; } 90 memset(vis,0,sizeof(vis)); 91 ans=inf; 92 dfs(sx,sy,0); 93 if (ans==inf) cout<<-1<<endl; 94 else cout<<ans<<endl; 95 } 96 return 0; 97 }