POJ 2221 - Frogger's For Dinner

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

概要

\(10 \times 10\) のグリッドが与えられ、1行目と10行目は路肩であり2行目から9行目は道を表わしている。 道を渡るとき、ある列を決めたら単位時間毎にその列を1歩ずつしか進めない。 道を走っている車に轢かれないように渡れるかどうか答える。 2行目から5行目の車は左側に向かって走っており、6行目から9行目の車は右側に向かって走っている。

解法

やるだけ。

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 bool ok(int road[10][10])
 6 {
 7   for (int c = 0; c < 10; c++) {
 8     for (int i = 1; i < 10; i++) {
 9       for (int j = 0; j < 10; j++) {
10         if (road[i][j] == 0) {
11           continue;
12         }
13         int beg = j + (i-1)*road[i][j];
14         int end = j + i*road[i][j];
15         if (beg >= end) {
16           beg = (beg%10+10)%10;
17           end = (end%10+10)%10;
18           if (beg >= end) {
19             if (end <= c && c <= beg) {
20               goto FAILED;
21             }
22           } else {
23             if (c <= beg || end <= c) {
24               goto FAILED;
25             }
26           }
27         } else {
28           beg = (beg%10+10)%10;
29           end = (end%10+10)%10;
30           if (beg <= end) {
31             if (beg <= c && c <= end) {
32               goto FAILED;
33             }
34           } else {
35             if (c <= end || beg <= c) {
36               goto FAILED;
37             }
38           }
39         }
40       }
41     }
42     return true;
43 FAILED:
44     ;
45   }
46   return false;
47 }
48 
49 int main()
50 {
51   for (string dummy; cin >> dummy;) {
52     int road[10][10];
53     fill_n(road[0], 10, 0);
54     fill_n(road[9], 10, 0);
55     for (int i = 1; i < 9; i++) {
56       for (int j = 0; j < 10; j++) {
57         cin >> road[i][j];
58         if (i <= 4) {
59           road[i][j] = -road[i][j];
60         }
61       }
62     }
63     cin >> dummy;
64     cout << (ok(road) ? "LEFTOVER POSSUM" : "FROGGER") << endl;
65   }
66   return 0;
67 }