POJ 1970 - The Game

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

概要

\(19 \times 19\) の盤面が与えられ、その上に白い石か黒い石が乗っている。 このゲームでは、同じ色の石を縦・横・対角線方向に5つ連続して並べたほうが勝ちである。 ただし、その方向に5つより多く同じ色の石が並んでいてはならない。 このとき、与えられた盤面で黒が勝っているか、白が勝っているか、どちらも勝っていないかを答える。 また、どちらかが勝っている場合は、勝っている5つの石のうち最も左の位置 (縦方向に並んでいる場合は最も上の位置) も答える。

制約

解法

やるだけ。 盤面の外の位置に対して 0 を返すような関数を定義しておくとやりやすいかも。

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct board
 7 {
 8   int grid[19][19];
 9 
10   bool win_p(int& i, int& j, int self) const
11   {
12     for (i = 0; i < 19; i++) {
13       for (j = 0; j < 19; j++) {
14         for (int d = 0; d < 4; d++) {
15           int a[5];
16           static const int di[] = {-1, 0, 1, 1};
17           static const int dj[] = {1, 1, 1, 0};
18           for (int k = 0; k < 5; k++) {
19             a[k] = at(i + di[d]*k, j + dj[d]*k);
20           }
21           if (count(a, a+5, self) == 5
22               && at(i - di[d], j - dj[d]) != self
23               && at(i + di[d]*5, j + dj[d]*5) != self) {
24             return true;
25           }
26         }
27       }
28     }
29     return false;
30   }
31 
32   int at(int i, int j) const
33   {
34     if (0 <= i && i < 19 && 0 <= j && j < 19) {
35       return grid[i][j];
36     } else {
37       return 0;
38     }
39   }
40 };
41 
42 int main()
43 {
44   int T;
45   cin >> T;
46   while (T-- > 0) {
47     board b;
48     for (int i = 0; i < 19; i++) {
49       for (int j = 0; j < 19; j++) {
50         cin >> b.grid[i][j];
51       }
52     }
53     int i, j;
54     if (b.win_p(i, j, 1)) {
55       cout << 1 << endl;
56       cout << i+1 << " " << j+1 << endl;
57     } else if (b.win_p(i, j, 2)) {
58       cout << 2 << endl;
59       cout << i+1 << " " << j+1 << endl;
60     } else {
61       cout << 0 << endl;
62     }
63   }
64   return 0;
65 }
poj/1970.cc