Game Theory (HackerRank) : A Chessboard Game
問題
Programming Problems and Competitions :: HackerRank
15*15マスの盤に1つの駒が置いてある。
駒が(x, y)にあるとすると、その駒は (x-2, y+1), (x-2, y-1), (x+1, y-2), (x-1, x-2) に移動できる。(図を参照)
2人のプレイヤーはそれぞれのターンで駒を1回移動させ、先に移動させられなくなった方の負け。
どちらが勝つか。
解法
素直にGrundy数を求める。
実装
#include <bits/stdc++.h> using namespace std; #define int long long const int dx[4] = {-2, -2, 1, -1}, dy[4] = {1, -1, -2, -2}; int T, X, Y; int memo[15][15]; int Grundy(int x, int y) { if (x < 0 || 15 <= x || y < 0 || 15 <= y) return -1; if (memo[x][y] != -1) return memo[x][y]; set<int> s; for (int i = 0; i < 4; i++) { int ret = Grundy(x + dx[i], y + dy[i]); if (ret >= 0) s.insert(ret); } int res = 0; while (s.count(res)) res++; return memo[x][y] = res; } signed main() { cin >> T; for (int tc = 0; tc < T; tc++) { fill((int*)memo, (int*)memo + 15*15, -1); cin >> X >> Y; X--; Y--; puts(Grundy(X, Y) ? "First" : "Second"); } return 0; }