hogecoder

tsutaj 競技プログラミングの記録

AtCoder Regular Contest 038 B: マス目と駒

ちょっと迷ってしまったので。

問題概要

原文を参照してください → B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder

解説

rec[i][j] := (i, j) で手番が回ってきた人は勝つか負けるか? となるような配列を作ります。

あるマス  (i, j) について、この値は以下のように決定できます。

  • 1 ターンで行ける範囲に「負け」を表すマスが少なくとも 1 つある場合、勝ち
  • 上記に当てはまらない場合 (移動先の候補がない時も含む)、負け

少しわかりにくいと思うので解説すると、 (i, j) から 1 ターン動いた先で手番が回ってくる人、つまり「相手」が負け確定になるようなマスがある場合、そこに移動することで自分が勝ち確定になります。反対に、そのようなマスが 1 つもない場合は自分が負け確定になります。あとはこれを右下からメモ化再帰で求めていけば良いです。

ソースコード

int h, w;
char board[110][110];

// rec[i][j] := (i, j) から始めたら勝つか負けるか?
int rec[110][110];

int dx[] = {0, 1, 1};
int dy[] = {1, 0, 1};

int solve(int x, int y) {
    int &r = rec[x][y];
    if(r != -1) return r;
    r = 1;
    rep(i,0,3) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx == h || ny == w || board[nx][ny] == '#') continue;
        if(solve(nx, ny) == 1) r = 0;
    }
    return r;
}

signed main() {
    cin >> h >> w;
    rep(i,0,h) rep(j,0,w) cin >> board[i][j];
    memset(rec, -1, sizeof(rec));
    cout << (solve(0, 0) ? "Second" : "First") << endl;
    return 0;
}

先攻か後攻かの情報も保持したほうがいいのかな、とか色々考えていたらすんなり書けませんでした。ゲームの問題はもう少し慣れが必要そうです。