問題:
http://poj.org/problem?id=2312思路:
這題糾結(jié)了...一上午都沒寫出來，原以為很簡單的(其實(shí)，很多人都說是簡單題，艾)
首先想到的是廣搜，因?yàn)槭乔髲脑袋c(diǎn)到目的地的最小步數(shù)嘛，典型的BFS，結(jié)果卻始終不知道如何表示每個(gè)狀態(tài)以及狀態(tài)間的判重
既然廣搜不會(huì)，那就深搜吧，恩，很快就寫出代碼，結(jié)果TLE...
無奈，只好在網(wǎng)上找解法，發(fā)現(xiàn)一種相當(dāng)不錯(cuò)的BFS代碼:
隊(duì)列的狀態(tài)只需要保存當(dāng)前位置即可，另外用數(shù)組best[][]表示目前從源點(diǎn)到達(dá)每個(gè)點(diǎn)的最小步數(shù)
在從當(dāng)前點(diǎn)擴(kuò)展的時(shí)候，只將有最小步數(shù)更新的點(diǎn)加入隊(duì)列
這樣當(dāng)BFS搜索結(jié)束時(shí)，每個(gè)best[i][j]都保存了從源點(diǎn)到點(diǎn)[i][j]的最短步數(shù)
原來還有這樣寫B(tài)FS的方法，又學(xué)習(xí)了(*^__^*) 嘻嘻……
上述算法有點(diǎn)類似于求最短路徑呵呵
而，事實(shí)上，這題是可以很容易轉(zhuǎn)化成圖論求單源最短路徑的
代碼:
1 /* 32MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 301
6 #define QUEUE_SIZE 90001
7 #define INF 0x7FFFFFFF
8 #define is_valid(x, y) ((x)>=0 && (x)<M && (y)>=0 && (y)<N)
9 char map[MAX_LEN][MAX_LEN];
10 const int dx[] = {0, 0, -1, 1};
11 const int dy[] = {-1, 1, 0, 0};
12 int M, N;
13 int you_x, you_y, target_x, target_y;
14 int best[MAX_LEN][MAX_LEN]; /* important, best[i][j] stores the current 'best solution' at map[i][j] */
15 struct Node {
16 int x, y;
17 } queue[QUEUE_SIZE];
18
19 int
20 bfs()
21 {
22 int i, next_x, next_y, cur, head, tail;
23 struct Node node;
24 head = -1;
25 tail = 0;
26 queue[tail].x = you_x;
27 queue[tail].y = you_y;
28 best[you_x][you_y] = 0;
29 while(head < tail) {
30 ++head;
31 cur = best[queue[head].x][queue[head].y];
32 for(i=0; i<4; i++) {
33 node.x = queue[head].x + dx[i];
34 node.y = queue[head].y + dy[i];
35 if(is_valid(node.x, node.y)) {
36 /* excellent, only push node which can be updated in 'best' into the queue */
37 if(map[node.x][node.y] == 'E' || map[node.x][node.y] == 'T') {
38 if(best[node.x][node.y] > cur+1) {
39 best[node.x][node.y] = cur+1;
40 ++tail;
41 queue[tail] = node;
42 }
43 } else if(map[node.x][node.y] == 'B') {
44 if(best[node.x][node.y] > cur+2) {
45 best[node.x][node.y] = cur+2;
46 ++tail;
47 queue[tail] = node;
48 }
49 }
50 }
51 }
52 }
53 }
54
55 int
56 main(int argc, char **argv)
57 {
58 int i, j;
59 while(scanf("%d %d", &M, &N)!=EOF && M && N) {
60 for(i=0; i<M; i++) {
61 scanf("%s", map[i]);
62 for(j=0; j<N; j++) {
63 if(map[i][j] == 'Y') {
64 you_x = i;
65 you_y = j;
66 } else if(map[i][j] == 'T') {
67 target_x = i;
68 target_y = j;
69 }
70 best[i][j] = INF;
71 }
72 }
73 bfs();
74 printf("%d\n", best[target_x][target_y]==INF ? -1 : best[target_x][target_y]);
75 }
76 }