ARC 038 B マス目と駒

2015/05/03 (Sun) ARC AtCoder ゲーム DP

問題

日本語

方針

あるマスのにいるときの勝ち負けは、 そこから遷移できるマスの中に 1 つでも勝ちが確定しているマスがあれば勝ち、 そうでなければ負けという DP で求められる。

これも Grundy 数で解けるらしい…

実装

int h,w;
char g[111][111];
int dp[111][111];
int dx[] = {0,1,1};
int dy[] = {1,0,1};
bool inside(int x, int y){
    return 0 <= x && x < w && 0 <= y && y <= h;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    rep(i,h) cin >> g[i];
    for(int y=h-1;y>=0;y--){
        for(int x=w-1;x>=0;x--){
            int win = 0;
            int lose = 0;
            rep(d,3){
                int nx = x+dx[d];
                int ny = y+dy[d];
                if(!inside(nx,ny)) continue;
                if(g[ny][nx] == '#') continue;
                if(dp[ny][nx]) win++;
                else lose++;
            }
            if(win==0){
                dp[y][x] = 1;
            } else {
                dp[y][x] = 0;
            }
        }
    }
    rep(i,h){
        dump(vi(dp[i],dp[i]+w));
    }
    puts(dp[0][0] ? "Second" : "First");
}