問(wèn)題:
http://poj.org/problem?id=2312思路:
在
http://www.shnenglu.com/Joe/archive/2010/10/23/130973.html中，參考網(wǎng)上代碼采用了一種"新"的BFS方法來(lái)解題，該方法的一個(gè)缺點(diǎn)在于每個(gè)點(diǎn)可能多次進(jìn)入隊(duì)列，這也直接導(dǎo)致了單個(gè)點(diǎn)的多次擴(kuò)展
其實(shí)，這題可以采用原始的BFS方法來(lái)做，只是不能再用普通的隊(duì)列，而需要使用優(yōu)先級(jí)隊(duì)列
通過(guò)這題，使我對(duì)于寬度優(yōu)先搜索有了新的認(rèn)識(shí)
普通的BFS之所以能夠找到最小的步數(shù)，關(guān)鍵在于它是單步擴(kuò)展的，也就是說(shuō)它首先羅列出所有在一步之內(nèi)可以到達(dá)的點(diǎn)，然后再羅列所有在兩步之內(nèi)可以到達(dá)的點(diǎn)，類似于"1-1-1...-2-2-2...-3-3-3..."的方式
這題在擴(kuò)展的時(shí)候并非都是一步，所以普通的BFS并不能找出正確的解，例如:
Y B
E T
假如我們以右、下、左、上的順序進(jìn)行擴(kuò)展，那么我們將得出結(jié)果是3，而事實(shí)上只需要2
優(yōu)先級(jí)隊(duì)列之所以能夠找出正確解，是因?yàn)樗ＷC我們始終從最小步數(shù)的點(diǎn)開始擴(kuò)展
代碼(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 }