問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1915思路:
典型的寬度優(yōu)先搜索
貌似求解最優(yōu)問題的這種題目用寬度優(yōu)先搜索比較合適，如果更改為深度優(yōu)先搜索，那么必須求出所有的解才能得到最優(yōu)解(通過遞歸調(diào)用樹可以清晰的明白這點(diǎn))
1 int
2 bfs()
3 {
4 int i, tx, ty, ttx, tty, cur;
5 ++tail;
6 queue[tail].x = start_x;
7 queue[tail].y = start_y;
8 vstd_min[start_x][start_y] = 0;
9 while(head < tail) {
10 ++head;
11 tx = queue[head].x;
12 ty = queue[head].y;
13 cur = vstd_min[tx][ty];
14 if(tx==end_x && ty==end_y)
15 return cur;
16 for(i=0; i<8; i++) {
17 ttx = tx + dxy[i][0];
18 tty = ty + dxy[i][1];
19 if(is_valid(ttx, tty) && vstd_min[ttx][tty]==0) {
20 ++tail;
21 queue[tail].x = ttx;
22 queue[tail].y = tty;
23 vstd_min[ttx][tty] = cur+1;
24 }
25 }
26 }
27 return 32767;
28 }