問題:
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 }