POJ 2766 - Laserbox

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

概要

n * n のグリッド上に r 個の right-turner がある． right-turner はそこマスに飛んできたレーザーを右に90度回転させる．

n * n のグリッドの外側のあるマスから内側にレーザーを発射したとき，最終的にグリッドがら出ていく場所を答える．

制約

解法

やるだけ．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int T;
 8   cin >> T;
 9   while (T-- > 0) {
10     int N, R;
11     cin >> N >> R;
12     vector<vector<int> > grid(N+2, vector<int>(N+2, 0));
13     for (int i = 0; i < R; i++) {
14       int r, c;
15       cin >> r >> c;
16       grid[r][c] = 1;
17     }
18     int r, c;
19     cin >> r >> c;
20     int d;
21     if (r == 0) {
22       d = 2;
23     } else if (r == N+1) {
24       d = 0;
25     } else if (c == 0) {
26       d = 1;
27     } else if (c == N+1) {
28       d = 3;
29     } else {
30       throw "invalid input";
31     }
32 
33     static const int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
34     r += dr[d];
35     c += dc[d];
36     while (0 < r && r < N+1 && 0 < c && c < N+1) {
37       if (grid[r][c]) {
38         // turner
39         d = (d+1)%4;
40       }
41       r += dr[d];
42       c += dc[d];
43     }
44     cout << r << ' ' << c << endl;
45   }
46   return 0;
47 }
poj/2766.cc