ARC038 B問題 マス目と駒

ゲーム系の苦手な問題。

先手が勝てば勝ち、もし負けることがあれば、負け、という感じで考えるといいっぽい？

まず全探索のイメージから入って、そのあとメモ化できるからメモ化しよう、みたいに考えるのがいい。全探索を考えるのが全てにおいて最初。

int H, W;
string S[101];
int memo[101][101];

bool dfs(int x, int y){
    if(memo[y][x] != -1) return (bool)memo[y][x];
    if(x < 0 || x >= W || y < 0 || y >= H || S[y][x] == '#') 
        return memo[y][x] = 1;
    if(dfs(x+1, y) == false) return memo[y][x] = 1;
    if(dfs(x+1, y+1) == false) return memo[y][x] = 1;
    if(dfs(x, y+1) == false) return memo[y][x] = 1;
    return memo[y][x] = 0;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    memset(memo, -1, sizeof(memo));
    cin >> H >> W;
    for(int i=0; i<H; i++){
        cin >> S[i];
    }
    cout << (dfs(0, 0) ? "First" : "Second") << endl;
}