読者です 読者をやめる 読者になる 読者になる

4bitにっき

ぽよ

Game Theory (HackerRank) : A Chessboard Game

Grundy数 DP

問題

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回移動させ、先に移動させられなくなった方の負け。
どちらが勝つか。

 テストケース数T \leq 15^2
 1 \leq x, y \leq 15 ((x, y)は駒の初期位置)

解法

素直に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;
}