ARC 038 B

今回はこの問題。

arc038.contest.atcoder.jp

h * wのマスがあります。このマス上には障害物があることがあり、「#」で表されます。
(1, 1)のマスに駒をおきます。駒が(i, j)にあるとき、プレイヤーは交互にこのマスを(i + 1, j), (i, j + 1), (i + 1, j + 1)のいずれかに動かすことができます。障害物のあるマスには動かせません。また、範囲外には動かせません。自分のターンの際に駒を動かせない時、その人の負けになります。
h, wの値と、マスの状態が与えられます。プレイヤーが二人とも最善を尽くした場合、どちらが勝つか判断しなさい、という問題です。

回答はこちら。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int h, w;
    char s[101][101];
    int result[101][101][2] = {};
     
    int solve(int x, int y, int player)
    {
        if(result[x][y][player] != 0) return result[x][y][player];
        int dx[3] = {0, 1, 1};
        int dy[3] = {1, 0, 1};
        int ans;
        if(player == 0) ans = -1;
        else ans = 1;
        for(int i = 0; i < 3; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx > h || ny > w || s[nx][ny] == '#') continue;
            if(player == 0) ans = max(ans, solve(nx, ny, 1));
            else ans = min(ans, solve(nx, ny, 0));
        }
        result[x][y][player] = ans;
        return ans;
    }
     
    int main()
    {
        
        cin >> h >> w;
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                cin >> s[i][j];
            }
        }
        if(solve(1, 1, 0) == 1) cout << "First" << endl;
        else cout << "Second" << endl;
     
        return 0;
    }

ゲーム木とよばれる手法(?)を使ってときます。現状から遷移できうる状態を全探索して、最善手をとる、という感じの方法です。
同じところを何度も探索するのは無駄なので、記録していくことにしました。result[i][j][k]には、(i, j)のマスに駒があり、k = 0のときはプレイヤー1、k = 1のときはプレイヤー2のターンである際に、この後最善手を取るとどちらが勝つか、を記録しています。この値が1ならばプレイヤー1が、-1ならばプレイヤー2が勝ちます。
solve関数のansについて、player = 0のときは初期値を-1にしていますが、まず最悪の場合である相手が勝つ、という予測?設定?をしておいて、maxを用いて書き換えると楽な気がします。これ以上進めない、つまりプレイヤー1が負けるときは、ansの値が変更されないということになるので、そのまま-1を返すことができて都合がいいです。プレイヤー2の場合はこれを逆にしただけです。