ARC 038 B マス目と駒
問題
方針
あるマスのにいるときの勝ち負けは、 そこから遷移できるマスの中に 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");
}