SOJ 1135. 飞跃原野

 1 #include <cstdio>
 2 #include <queue>
 3 using namespace std;
 4 const int maxm = 100;
 5 const int maxn = 100;
 6 
 7 char altas[maxm][maxn + 1];
 8 int max_energy[maxm][maxn];
 9 
10 const int dm = 100000;
11 const int dn = 1000;
12 const int dd = 1;
13 
14 // 0-右，1-左，2-上，3-下
15 int dx[4] = {0, 0, -1, 1};
16 int dy[4] = {1, -1, 0, 0};
17 
18 void init(int m, int n) {
19     for (int i = 0; i < m; ++i)
20         for (int j = 0; j < n; ++j)
21             max_energy[i][j] = -1;
22 }
23 
24 int main() {
25     int m, n, d;
26     while (scanf("%d%d%d", &m, &n, &d) != EOF) {
27         init(m, n); // 初始化
28         for (int i = 0; i < m; ++i) scanf("%s", altas[i]);  // 输入地图
29 
30         if (m == 1 && n == 1) { // 特殊情况判断
31             printf("0\n");
32             continue;
33         }
34         // bfs
35         int start = 0 * dm + 0 * dn + d * dd;
36         max_energy[0][0] = d;   // 初始状态的d最充足
37         queue<int> que; que.push(start);
38         int unit = 0;
39         bool find = false;
40         while (!que.empty() && !find) {
41             ++unit;
42             int size = que.size();
43             while (size-- && !find) {
44                 int state = que.front(); que.pop(); // 获取状态
45                 int r = state / dm; // 状态还原
46                 int c = state % dm / dn;
47                 int e = state % dn;
48 
49                 // 找下一步可走位置
50                 // 先环顾最近的四个方向一圈
51                 for (int i = 0; i < 4 && !find; ++i) {
52                     int next_m = r + dx[i];
53                     int next_n = c + dy[i];
54                     if (0 <= next_m && next_m < m && 0 <= next_n && next_n < n && altas[next_m][next_n] == ‘P‘) {
55                         if (e > max_energy[next_m][next_n]) {   // 后来的如果能量更加充足，可以重新启动该点
56                             max_energy[next_m][next_n] = e;
57                             int next_state = next_m * dm + next_n * dn + e * dd;
58                             que.push(next_state);
59                             if (next_m == m - 1 && next_n == n - 1) find = true;
60                         }
61                     }
62                 }
63                 // 再考虑飞行的可能
64                 // 0-右，1-左，2-上，3-下
65                 for (int i = 0; i < 4 && !find; ++i) {
66                     for (int j = 2; j <= e && !find; ++j) {
67                         int next_m = r + dx[i] * j;
68                         int next_n = c + dy[i] * j;
69                         if (0 <= next_m && next_m < m && 0 <= next_n && next_n < n) {
70                             if (altas[next_m][next_n] == ‘P‘) {
71                                 if (e - j > max_energy[next_m][next_n]) {
72                                     max_energy[next_m][next_n] = e - j;
73                                     int next_state = next_m * dm + next_n * dn + (e - j) * dd;
74                                     que.push(next_state);
75                                     if (next_m == m - 1 && next_n == n - 1) find = true;
76                                 }
77                             }
78                         } else {
79                             break;
80                         }
81                     }
82                 }
83 
84             }
85         }
86 
87         if (find) printf("%d\n", unit);
88         else printf("impossible\n");
89     }
90     return 0;
91 }