【POJ 3009 Curling2.0 迷宫寻径 DFS】

http://poj.org/problem?id=3009

模拟冰壶的移动，给出到达终点的最少投掷次数（不可达时为-1）。

具体移动规则如下：

每次选四个方向之一，沿此方向一直前进，直到撞到block或出界或抵达目标位置。

　　如果撞到block，冰壶停在block的前一个位置，block消失，此时可改变冰壶的移动方向（重新投掷一次）；

　　如果出界，则这条移动路径以失败结束；

　　如果抵达目标位置，则记录这条移动路径一共投掷的次数。

投掷次数不超过10次的为成功路径。

如果存在成功路径，输出最少的投掷次数；不存在则输出-1。

代码如下，由于数据量小，可用DFS得到所有解然后取最小值；注意回溯时还原修改过的block：

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4
 5 const int MAX_N = 22;
 6
 7 int n, m;
 8 int G[MAX_N][MAX_N];
 9 int dx[]={0, 0, 1,-1}, dy[]={1, -1, 0, 0};
10 int sx, sy, gx, gy;
11 int min_ans;
12
13
14 bool inside(int x, int y){
15     if(x<0 || x>=n || y<0 || y>=m) return false;
16     return true;
17 }
18
19 void dfs(int x, int y, int cnt){
20     if(cnt > 10) return ;
21     for(int i=0; i<4; i++){
22         int nx = x + dx[i];
23         int ny = y + dy[i];
24         if(!inside(x, y)) continue; //出界
25         if(G[nx][ny] == 1) continue; //block
26         else{
27             while(inside(nx, ny) && G[nx][ny] != 1 && G[nx][ny] != 3){
28                 nx += dx[i];
29                 ny += dy[i]; //沿此方向走到block为止
30             }
31             if(!inside(nx, ny)) continue; //此方向最终出界
32             if(G[nx][ny] == 3){
33                 min_ans = cnt<min_ans ? cnt : min_ans;
34                 continue; //此方向中途命中
35             }
36
37             G[nx][ny] = 0; //block消失
38             nx -= dx[i];
39             ny -= dy[i]; //抵达此方向最后一个合法位置，block的前一个
40             //printf("%d %d\n", dx[i], dy[i]);
41             dfs(nx, ny, cnt+1);
42             nx += dx[i];
43             ny += dy[i];
44             G[nx][ny] = 1; //还原，回溯
45         }
46     }
47     return ;
48 }
49
50 int main()
51 {
52     freopen("3009.txt", "r", stdin);
53     while(scanf("%d%d", &m, &n) != EOF){
54         if(m==0 && n==0) break;
55         for(int i=0; i<n; i++){
56             for(int j=0; j<m; j++){
57                 scanf("%d", &G[i][j]);
58                 if(G[i][j] == 2){
59                     sx = i;
60                     sy = j;
61                 }else if(G[i][j] == 3){
62                     gx = i;
63                     gy = j;
64                 }
65             }
66         }
67
68         min_ans = 29; //任意大于10的值
69         dfs(sx, sy, 1); //投掷第一次
70         if(min_ans > 10) min_ans = -1;
71         printf("%d\n", min_ans);
72     }
73     return 0;
74 }

注意记这一类搜索的框架，以及联系算法课学过的回溯法的基本概念，如约束条件、活结点等。