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