問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3009思路:
這題要求進(jìn)行一個(gè)簡(jiǎn)單的游戲，判斷最優(yōu)步數(shù)。通常來(lái)說(shuō)，這種判斷最短步驟的問(wèn)題可以使用廣度優(yōu)先搜索解決(bfs),由于題目中地圖會(huì)由于游戲的進(jìn)行發(fā)生變化，使用bfs會(huì)比較麻煩（需要記錄地圖狀態(tài)），注意到題目中有一個(gè)條件：只能在10步以內(nèi)完成游戲，于是我們可以考慮使用深度優(yōu)先搜索（dfs）+限制步數(shù)來(lái)完成。簡(jiǎn)單的說(shuō)：就是我們遍歷整個(gè)搜索樹(shù)尋找可能解中的最優(yōu)步數(shù)，但當(dāng)搜索樹(shù)深度大于10時(shí)則不必繼續(xù)搜索下去。
代碼:
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 }