SRM588 Div2 Hard "GameInDarknessDiv2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12710
訳
アリスとボブは四角いボードを使ったゲームで遊んでいる。行と列には、両方とも0から始まる番号がつけられている。これより、i番目の列、j番目の行のマスを( i, j )と表す。マス( 0, 0 )とは左上の隅のマスの事である。ボードは壁マスと空マスで構成されており、このゲームは空マスだけを使って遊ぶ。
ゲームは以下のようにして遊ぶ。ボード上には、アリスとボブの駒が、1つずつ置かれている。ゲーム開始当初、その2つの駒が同じマスに置かれている事はない。プレイヤーは交互に駒を動かしていく。初めに動かすのはアリスである。駒は、現在のマスの隣り合うマスに動かしていく。(壁マスには動かす事はできない)なお、手番が回ってきたら、駒は必ず動かす必要があり、その場に留まることはできない。
2つの駒が、同じマスに到達すれば、アリスの勝ちである。もし、アリスが(下記で説明するように)ギブアップしたらボブの勝ちである。
あなたはボードの状態を示す、Stringの配列 fieldが与えられる。field[i][j]はマス( i, j )に対応しており、それが'.'であれば空マス、'#'であれば壁マスであることを示す。また、'A'はアリスの駒の初期位置で、'B'はボブの駒の初期位置である。当然ながら、'A' 'B' のマスは壁マスではなく、空マスである。
このゲームはちょっと変わっていて、ボードは完全に闇に包まれているのである。アリスとボブはお互いに初期位置は分かっている。アリスはボブの現在の位置を知るすべはない。しかし、ボブはアリスがこのゲームでどう動いてくるのかを正確に把握している。
あなたはStringの配列 movesが与えられる。これはアリスが行うであろう駒の動かし方を示す。movesの全ての要素を連結した文字列をMとする。M[i-1]は、アリスのiターン目に対応しており、その文字によって、アリスは下記のように駒を動かしてくる。
'U' : 上に動かす 'D' : 下に動かす 'L' : 左に動かす 'R' : 右に動かす
この情報では、アリスは壁に向かって進んだり、ボードをはみ出したりせず、空のマスを移動する事が保証される。アリスがMの文字を使い切ってもボブを捕えきれない場合、アリスはギブアップし、ボブの勝利となる。
ボブが最善を尽くしたときに、ボブが勝つのならば"Bob wins"を、そうでなければ"Alice wins"を返せ。
制約
1 <= マスの行・列 <= 50
1 <= アリスの行動回数 <= 2500
考えた事
DP[ボブのx位置][ボブのy位置][ターン数]のdpでいける。
ボブの進む先に、アリスがいてはいけない。また、ボブの動き出し時、アリスと同じマスにいてはいけない。
ソースコード
int N; int H, W; vector<string> F; int xs[2550], ys[2550]; // iターン時のアリスの位置 int memo[55][55][2550]; // tターン目に(x, y)に居たときBobは逃げ切れるか? bool dfs( int x, int y, int t ){ if( memo[x][y][t] != -1 ){ return memo[x][y][t] == 1; } bool res = false; // ターンを越してたら勝ち if( N < t ){ res = true; } // Aliceが同じマスにいたら負け else if( x == xs[t+1] && y == ys[t+1] ){ res = false; } // 上下左右試す else{ int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 }; for( int d = 0; d < 4; d++ ){ int nx = x + dx[d]; int ny = y + dy[d]; // フィールドからはみ出してない? if( nx < 0 || W <= nx || ny < 0 || H <= ny ) continue; // そこ壁じゃない? if( F[ny][nx] == '#' ) continue; // そこにAliceいない? if( nx == xs[t+1] && ny == ys[t+1] ) continue; // 移動を試みる res |= dfs( nx, ny, t + 1 ); } } // メモ memo[x][y][t] = res ? 1 : 0; return res; } class GameInDarknessDiv2 { public: string check(vector <string> field, vector <string> moves){ string move; for( int i = 0; i < moves.size(); i++ ){ move += moves[i]; } N = move.length(); H = field.size(); W = field[0].length(); F = field; // 初期位置取得 int ax, ay, bx, by; for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( F[y][x] == 'A' ){ ax = x; ay = y; } if( F[y][x] == 'B' ){ bx = x; by = y; } } } // xs, ys初期化 xs[0] = ax; ys[0] = ay; for( int i = 1; i <= N; i++ ){ int dx = 0, dy = 0; if( move[i-1] == 'U' ){ dy = -1; } if( move[i-1] == 'D' ){ dy = 1; } if( move[i-1] == 'L' ){ dx = -1; } if( move[i-1] == 'R' ){ dx = 1; } xs[i] = xs[i-1] + dx; ys[i] = ys[i-1] + dy; } // dfs memset( memo, -1, sizeof(memo) ); bool bobwin = dfs( bx, by, 0 ); return bobwin ? "Bob wins" : "Alice wins"; } };