ARC038 B - マス目と駒

概要

H×Wマスのいくつかのマスに壁があり、(1, 1)にコマがある状態でゲームを行う。
先手と後手が交互に下記の操作を繰り返す。先に操作できなくなった方を負けとする。先手と後手どちらが勝つかを解答せよ。

• コマを右・右下・下のいずれかの方向で、かつ壁でないマスに動かす

制約

1 ≦ H, W ≦ 100

方針

ゲームDP。
dp[i][j]：(i+1, j+1)からゲームを開始したときに先手が勝つかどうか　としてDPしてゆく。

ポイント
・盤面全体の右下マスは先手負け、同様に最下行で右マスが壁でも先手負け、最右列で下マスが壁でも先手負け
・あるマスの右・右下・下のいずれかのマスが先手負けならそのマス自体は先手勝ち、ただし壁のマスはカウントしない(先手勝ちとしておくとよい)
・あるマスの右・右下・下のすべてのマスが先手勝ちならそのマス自体は先手負けにならざるを得ない

DPの例
入力例2
....
...#
....
.#..

DP配列
0110
1101
1011
0110

結果
Second（(1, 1)が0なので後手勝ち）

感想

このDPコンの問題と解き方が似ています。
misora192.hatenablog.com

解説はメモ化再帰でしたが、下の行・右の列から計算することで計算順序を与えることができ、DPとして解くこともできました。

解答

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
void print(vector<vector<bool>> dp){
	int n = dp.size();
	int m = dp[0].size();
 
	rep(i, n){
		rep(j, m) {
			cout << dp[i][j] << (j == m-1 ? "\n" : "");
		}
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int H, W;
	cin >> H >> W;
 
	string S[H];
	rep(i, H) cin >> S[i];
 
	vector<vector<bool>> dp(H, vector<bool>(W, false));
	// bool dp[H][W];
	// rep(i, H) rep(j, W) dp[i][j] = false;
 
	for(int i = H - 1; i >= 0; i--){
		for(int j = W - 1; j >= 0; j--){
			if(S[i][j] == '#') {
				dp[i][j] = true;
				continue;
			}
 
			// vectorだとこれがうまくいかない
			// if(i+1 < H && j+1 < W) dp[i][j] |= !dp[i+1][j+1];
			// if(i < H && j+1 < W) dp[i][j] |= !dp[i][j+1];
			// if(i+1 < H && j < W) dp[i][j] |= !dp[i+1][j];
 
			if(i+1 < H && j+1 < W) dp[i][j] = dp[i][j] | !dp[i+1][j+1];
			if(i < H && j+1 < W) dp[i][j] = dp[i][j] | !dp[i][j+1];
			if(i+1 < H && j < W) dp[i][j] = dp[i][j] | !dp[i+1][j];
		}
	}
 
	// print(dp);
	cout << (dp[0][0] ? "First" : "Second") << endl;
}