问题:
http://poj.org/problem?id=2312思路:
在
http://www.cppblog.com/Joe/archive/2010/10/23/130973.html中，参考网上代码采用了一种"新"的BFS方法来解题，该方法的一个缺点在于每个点可能多次进入队列，这也直接导致了单个点的多次扩展
其实，这题可以采用原始的BFS方法来做，只是不能再用普通的队列，而需要使用优先级队列
通过这题，使我对于宽度优先搜索有了新的认识
普通的BFS之所以能够找到最小的步数，关键在于它是单步扩展的，也就是说它首先罗列出所有在一步之内可以到达的点，然后再罗列所有在两步之内可以到达的点，类似于"1-1-1...-2-2-2...-3-3-3..."的方式
这题在扩展的时候并非都是一步，所以普通的BFS并不能找出正确的解，例如:
Y B
E T
假如我们以右、下、左、上的顺序进行扩展，那么我们将得出结果是3，而事实上只需要2
优先级队列之所以能够找出正确解，是因为它保证我们始终从最小步数的点开始扩展
代码(C++)
1 /* 0MS */
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #include<queue> /* priority queue */
6 using namespace std;
7
8 #define MAX_LEN 301
9 #define is_valid(x, y) ((x)>=0 && (x)<M && (y)>=0 && (y)<N)
10 char map[MAX_LEN][MAX_LEN];
11 const int dx[] = {0, 0, -1, 1};
12 const int dy[] = {-1, 1, 0, 0};
13 int M, N;
14 int you_x, you_y, target_x, target_y;
15 int visited[MAX_LEN][MAX_LEN];
16 struct Node {
17 int x, y;
18 int steps;
19 bool operator<(const Node &item) const {
20 return steps > item.steps;
21 }
22 }cur, next;
23 priority_queue<Node> states;
24
25 int
26 bfs()
27 {
28 int i;
29 memset(visited, 0, sizeof(visited));
30 while(!states.empty()) /* empty the queue */
31 states.pop();
32 next.x = you_x;
33 next.y = you_y;
34 next.steps = 0;
35 visited[you_x][you_y] = 1;
36 states.push(next);
37 while(!states.empty()) {
38 cur = states.top();
39 states.pop();
40 if(cur.x==target_x && cur.y==target_y)
41 return cur.steps;
42 for(i=0; i<4; i++) {
43 next.x = cur.x + dx[i];
44 next.y = cur.y + dy[i];
45 if(!visited[next.x][next.y]) {
46 visited[next.x][next.y] = 1;
47 if(map[next.x][next.y]=='E' || map[next.x][next.y]=='T') {
48 next.steps = cur.steps+1;
49 states.push(next);
50 } else if(map[next.x][next.y]=='B') {
51 next.steps = cur.steps+2;
52 states.push(next);
53 }
54 }
55 }
56 }
57 return -1;
58 }
59
60 int
61 main(int argc, char **argv)
62 {
63 int i, j;
64 while(scanf("%d %d", &M, &N)!=EOF && M && N) {
65 for(i=0; i<M; i++) {
66 scanf("%s", map[i]);
67 for(j=0; j<N; j++) {
68 if(map[i][j] == 'Y') {
69 you_x = i;
70 you_y = j;
71 } else if(map[i][j] == 'T') {
72 target_x = i;
73 target_y = j;
74 }
75 }
76 }
77 printf("%d\n", bfs());
78 }
79 }