Hdoj 2364 Escape
单纯的bfs()，当然你也可以用dfs,只要你不怕超时或者你的剪枝够强大最好开一个三维的数组，记录每一个格子的每一个方向上的最小值，直到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]
补充：软件开发 , 其他 ,
