問題:
http://poj.org/problem?id=2312思路:
這題糾結了...一上午都沒寫出來，原以為很簡單的(其實，很多人都說是簡單題，艾)
首先想到的是廣搜，因為是求從源點到目的地的最小步數嘛，典型的BFS，結果卻始終不知道如何表示每個狀態以及狀態間的判重
既然廣搜不會，那就深搜吧，恩，很快就寫出代碼，結果TLE...
無奈，只好在網上找解法，發現一種相當不錯的BFS代碼:
隊列的狀態只需要保存當前位置即可，另外用數組best[][]表示目前從源點到達每個點的最小步數
在從當前點擴展的時候，只將有最小步數更新的點加入隊列
這樣當BFS搜索結束時，每個best[i][j]都保存了從源點到點[i][j]的最短步數
原來還有這樣寫BFS的方法，又學習了(*^__^*) 嘻嘻……
上述算法有點類似于求最短路徑呵呵
而，事實上，這題是可以很容易轉化成圖論求單源最短路徑的
代碼:
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 }