poj 3009 (深搜求最短路)

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 using namespace std;
 5 const int maxn = 22;
 6 struct Point{
 7     int r, c;
 8     Point(int r=-1, int c=-1):r(r),c(c){}
 9 };
10 Point s,t;
11 int W,H;
12 int G[maxn][maxn];
13 const int dr[] = {1,-1,0,0};
14 const int dc[] = {0,0,-1,1};
15 int ans  = 100000;
16 void dfs(int r,int c,int k){
17     if(k >= 10) return ;
18     for(int i = 0; i < 4; i++){
19         int nr = r;
20         int nc = c;
21         int is_walk = 0;
22         while(G[nr+dr[i]][nc+dc[i]]==0){
23             is_walk=1;
24             nr+=dr[i];
25             nc+=dc[i];
26             if(nr == t.r && nc == t.c){
27                 ans = min(ans,k+1);
28                 return ;
29             }
30         }
31         if(!is_walk)continue;
32         if(G[nr+dr[i]][nc+dc[i]] == 4)continue ;
33         if(G[nr+dr[i]][nc+dc[i]] == 1){
34             G[nr+dr[i]][nc+dc[i]] = 0;
35             dfs(nr,nc,k+1);
36             G[nr+dr[i]][nc+dc[i]] = 1;
37         }
38     }
39 }
40 int main(){
41     while(scanf("%d%d ", &W, &H) && (W || H)){
42         ans  = 100000;
43         for(int i = 1; i <= H; i++){
44             for(int j = 1; j <= W; j++)
45                 scanf("%d",&G[i][j]);
46         }
47         for(int i = 0; i <= W+1; i++)
48             G[0][i] = 4,G[H+1][i] = 4;
49         for(int i = 0; i <= H+1; i++)
50             G[i][0] = 4,G[i][W+1] = 4;
51         for(int i = 1; i <= H; i++){
52             for(int j = 1; j <= W; j++){
53                 if(G[i][j] == 2){
54                     s = Point(i,j);
55                     G[i][j] = 0;
56                 }
57                 else if (G[i][j] == 3){
58                     t = Point(i,j);
59                     G[i][j] = 0;
60                 }
61             }
62         }
63         dfs(s.r,s.c,0);
64         if(ans != 100000 && ans <= 10)printf("%dn",ans);
65         else printf("%dn",-1);
66     }
67     return 0;
68 }