POJ 1301 - The Umbrella Problem: 2054

http://poj.org/problem?id=1301

概要

\(x \times y\) のグリッドとその上のスタート地点およびゴール地点が与えられる。 スタート地点は 1 行目にあり、ここからプレイヤーは毎ターン1行下に移動しながら \(y\) 行目のゴール地点を目指す。 移動するとき、プレイヤーは隣接する列に移動することができる。

グリッド上にはレーザーガンがあり、最初は上の方向に発射しており、毎ターン時計回りに回転する。 これに当たるとプレイヤーは死んでしまう。

このとき、プレイヤーがゴール地点に辿り着けるかどうかを答える。

制約

解法

BFS するだけ。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <vector>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 struct triplet
 9 {
10   int i, j, k;
11   triplet(int a, int b, int c) : i(a), j(b), k(c) {}
12 };
13 
14 int main()
15 {
16   for (string s; cin >> s && s != "ENDOFINPUT";) {
17     int C, R;
18     cin >> C >> R;
19     vector<string> m(R);
20     for (int i = 0; i < R; i++) {
21       cin >> m[i];
22     }
23     cin >> s;
24 
25     queue<triplet> q;
26     static const int INF = 10000000;
27     static bool grid[10][10][4];
28     static int dist[10][10][4];
29     for (int i = 0; i < R; i++) {
30       for (int j = 0; j < C; j++) {
31         fill_n(dist[i][j], 4, INF);
32         fill_n(grid[i][j], 4, true);
33       }
34     }
35     for (int i = 0; i < R; i++) {
36       for (int j = 0; j < C; j++) {
37         switch (m[i][j]) {
38           case 'L':
39             dist[i][j][0] = 0;
40             q.push(triplet(i, j, 0));
41             break;
42           case 'S':
43             for (int k = 0; k < 4; k++) {
44               static const int dr[] = {-1, 0, 1, 0};
45               static const int dc[] = {0, 1, 0, -1};
46               for (int x = i, y = j; 0 <= x && x < R && 0 <= y && y < C; x += dr[k], y += dc[k]) {
47                 grid[x][y][k] = false;
48               }
49             }
50             break;
51           case 'P':
52             fill_n(grid[i][j], 4, false);
53             break;
54         }
55       }
56     }
57 
58     while (!q.empty()) {
59       const int r = q.front().i;
60       const int c = q.front().j;
61       const int t = q.front().k;
62       q.pop();
63       if (!grid[r][c][t]) {
64         continue;
65       }
66       if (m[r][c] == 'G') {
67         cout << "FERRET" << endl;
68         goto NEXT;
69       }
70       for (int d = -1; d <= 1; d++) {
71         const int i = r+1;
72         const int j = c+d;
73         const int dd = dist[r][c][t]+1;
74         const int k = dd % 4;
75         if (0 <= i && i < R && 0 <= j && j < C && grid[i][j][t] && grid[i][j][k] && dd < dist[i][j][k]) {
76           dist[i][j][k] = dd;
77           q.push(triplet(i, j, k));
78         }
79       }
80     }
81     cout << "GARRET" << endl;
82 NEXT:
83     ;
84   }
85   return 0;
86 }
poj/1301.cc