问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1915思路:
典型的宽度优先搜索
貌似求解最优问题的这种题目用宽度优先搜索比较合适，如果更改为深度优先搜索，那么必须求出所有的解才能得到最优解(通过递归调用树可以清晰的明白这点)
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 }