ちょっと迷ってしまったので。
問題概要
原文を参照してください → B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder
解説
rec[i][j] := (i, j) で手番が回ってきた人は勝つか負けるか?
となるような配列を作ります。
あるマス について、この値は以下のように決定できます。
- 1 ターンで行ける範囲に「負け」を表すマスが少なくとも 1 つある場合、勝ち
- 上記に当てはまらない場合 (移動先の候補がない時も含む)、負け
少しわかりにくいと思うので解説すると、 から 1 ターン動いた先で手番が回ってくる人、つまり「相手」が負け確定になるようなマスがある場合、そこに移動することで自分が勝ち確定になります。反対に、そのようなマスが 1 つもない場合は自分が負け確定になります。あとはこれを右下からメモ化再帰で求めていけば良いです。
ソースコード
int h, w; char board[110][110]; // rec[i][j] := (i, j) から始めたら勝つか負けるか? int rec[110][110]; int dx[] = {0, 1, 1}; int dy[] = {1, 0, 1}; int solve(int x, int y) { int &r = rec[x][y]; if(r != -1) return r; r = 1; rep(i,0,3) { int nx = x + dx[i], ny = y + dy[i]; if(nx == h || ny == w || board[nx][ny] == '#') continue; if(solve(nx, ny) == 1) r = 0; } return r; } signed main() { cin >> h >> w; rep(i,0,h) rep(j,0,w) cin >> board[i][j]; memset(rec, -1, sizeof(rec)); cout << (solve(0, 0) ? "Second" : "First") << endl; return 0; }
先攻か後攻かの情報も保持したほうがいいのかな、とか色々考えていたらすんなり書けませんでした。ゲームの問題はもう少し慣れが必要そうです。