單純的bfs()，當(dāng)然你也可以用dfs,只要你不怕超時(shí)或者你的剪枝夠強(qiáng)大
最好開一個(gè)三維的數(shù)組，記錄每一個(gè)格子的每一個(gè)方向上的最小值，直到bfs完成
具體看代碼，不做過多的解釋。
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 struct node
5 {
6 int x, y;
7 int step, dir;
8 };
9 int n, m;
10 int xi[4] = {0, 1, -1, 0};
11 int yi[4] = {1, 0, 0, -1};
12 int vist[82][82][4];
13 char map[82][82];
14 node start;
15 queue <node> q;
16 bool check(int dx, int dy)
17 {
18 if(dx >= 1 && dx <= n && dy >= 1 && dy <= m) return true;
19 else return false;
20 }
21 bool find(node a)
22 {
23 if ((a.x == 1 || a.x == n || a.y == 1 || a.y == m)) return true;
24 else return false;
25 }
26 int bfs()
27 {
28 while (!q.empty())q.pop();
29 memset(vist, 0, sizeof(vist));
30 start.dir = -1;
31 start.step = 0;
32 q.push(start);
33 node now, next;
34 bool flag = true;
35 int tmp;
36 while (!q.empty())
37 {
38 now = q.front();
39 q.pop();
40 if (find(now)) return now.step;
41
42 flag = false;
43 for (int i = 0 ; i < 4; i++)
44 {
45 if (now.dir == i) continue;
46 if (now.dir >=0 && 3-now.dir == i) continue;
47 next.x = now.x + xi[i];
48 next.y = now.y + yi[i];
49 next.step = now.step + 1;
50 if (check(next.x, next.y) && map[next.x][next.y] == '.' )
51 {
52 if (vist[next.x][next.y][i] == 0)
53 {
54 vist[next.x][next.y][i] = next.step;
55 next.dir = i;
56 q.push(next);
57 }
58 else if (vist[next.x][next.y][i] > next.step)
59 {
60 vist[next.x][next.y][i] = next.step;
61 next.dir = i;
62 q.push(next);
63 }
64 flag = true;
65 }
66 }
67 if (!flag)
68 {
69 int i = now.dir;
70 if (i < 0) return 0;
71 next.x = now.x + xi[i];
72 next.y = now.y + yi[i];
73 next.step = now.step + 1;
74 if (check(next.x, next.y) && map[next.x][next.y] == '.' )
75 {
76 if (vist[next.x][next.y][i] == 0)
77 {
78 vist[next.x][next.y][i] = next.step;
79 next.dir = i;
80 q.push(next);
81 }
82 else if (vist[next.x][next.y][i] > next.step)
83 {
84 vist[next.x][next.y][i] = next.step;
85 next.dir = i;
86 q.push(next);
87 }
88 flag = true;
89 }
90 }
91 }
92 return -1;
93 }
94 int main()
95 {
96 int cas;
97 scanf("%d", &cas);
98 while (cas--)
99 {
100 scanf("%d%d", &n, &m);
101 int i, j;
102 for (i = 1; i <= n; i++)
103 scanf("%s", map[i]+1);
104 for (i = 1; i <= n; i++)
105 for (j = 1; j <= m; j++)
106 {
107 if (map[i][j] == '@')
108 {
109 start.x = i;
110 start.y = j;
111 map[i][j] = '.';
112 }
113 }
114 int ans = bfs();
115 printf("%d\n", ans);
116 }
117 return 0;
118 }
119
posted on 2012-04-13 18:34
路修遠(yuǎn) 閱讀(1315)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
路修遠(yuǎn)