问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3009思路:
这题要求进行一个简单的游戏，判断最优步数。通常来说，这种判断最短步骤的问题可以使用广度优先搜索解决(bfs),由于题目中地图会由于游戏的进行发生变化，使用bfs会比较麻烦（需要记录地图状态），注意到题目中有一个条件：只能在10步以内完成游戏，于是我们可以考虑使用深度优先搜索（dfs）+限制步数来完成。简单的说：就是我们遍历整个搜索树寻找可能解中的最优步数，但当搜索树深度大于10时则不必继续搜索下去。
代码:
1 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
2 #define INF 100000
3 #define THROW_MAX 10
4 #define MAX_LEN 21
5 int row, col, start_x, start_y;
6 int board[MAX_LEN][MAX_LEN];
7 int min;
8 const int dx[] = {0, 0, -1, 1};
9 const int dy[] = {-1, 1, 0, 0};
10
11 void
12 dfs(int depth, int x, int y)
13 {
14 int i, tx, ty;
15 if(depth>=THROW_MAX || depth>=min) /* pruning */
16 return;
17 for(i=0; i<4; i++) {
18 tx = x;
19 ty = y;
20 if(board[tx+dx[i]][ty+dy[i]] == 1) /* block immediately */
21 continue;
22 do {
23 tx += dx[i];
24 ty += dy[i];
25 if(is_valid(tx, ty) && board[tx][ty] == 3) { /* end */
26 min = depth+1;
27 return;
28 }
29 } while(is_valid(tx, ty) && board[tx][ty]!=1);
30 if(is_valid(tx, ty)) {
31 board[tx][ty] = 0; /* the block disappears */
32 dfs(depth+1, tx-dx[i], ty-dy[i]);
33 board[tx][ty] = 1;
34 }
35 }
36 }