問題
<p>
アリスとボブは、r行およびc列のグリッドに分割された矩形ボードを持っています。 グリッドは、String []型sで記述されています。 Sの各文字は、一つのセルを表します。cellには4つのタイプがあります。
</p>
<ul class="org-ul">
<li>
'E'は終了を表しています。任意の数の終了、おそらくゼロがあるかもしれません。
</li>
<li>
'T'は正方形は単一のトークンが含まれていることを意味します。最初はボード全体に正確に一つのトークンが存在することになります。
</li>
<li>
'＃'は、障害物を表します。
</li>
<li>
'。'空のセルを表します。
</li>
</ul>
<p>
アリスとボブはこのボード上のゲームをプレイします。 ゲームはintkによってパラメータ化されます。トークンは、最初にその上に数kを持っています。 プレイヤーはアリスから始まる、ターンを交互にかかります。プレイヤーのターンは、以下のステップで構成されています。
</p>
<ul class="org-ul">
<li>
プレイヤーは、下、左、または右のトークン1平方を上に移動します。トークンは、ボードの端に行くことができない、それが障害物をcellに入力することはできません。
</li>
<li>
このトークンが出口にある場合、それはボードから消えます。
</li>
<li>
それ以外の場合は、トークンの数から1を引きます。トークンの数がゼロの場合、ボードから取り外します。
</li>
</ul>
<p>
行動を起こすことができない最初のプレーヤーがゲームを失います。 （すでにボードを去ったとき、トークンにもこだわっているときに発生します。）
</p>
<p>
アリスとボブの両方を最適にプレイすると仮定すると、あなたはString[]型のを与えられ、intkは、ゲームの勝者を計算します。 当選者の名前を返します：「アリス」または「ボブ」のいずれか。戻り値は、大文字と小文字が区別されることに注意してください。
</p>
方針
プレイヤーが2人いて、お互いに最適な戦略を取ったとき勝つのはどちらか、 みたいな問題は、WL-Algorithmsというものを利用して解くらしい.
<p>
[sourcecode language="cpp" title="" ] boolean isWinning(State pos){ State[] nextStates = { posから到達できる全ての次の状態 }; for(State s : nextStates){ if(!isWinning(s)) return true; } return false; } [/sourcecode]
</p>
<ul class="org-ul">
<li>
相手を必ず負けさせるような手が存在するなら現在の位置では勝ち決定。
</li>
<li>
そのような手がないないのであれば負け。
</li>
</ul>
<p>
参考リンクをはっておく. あとで勉強しよう.
</p>
<ul class="org-ul">
<li>
<a href="https://d.hatena.ne.jp/nanikaka/20120524/1337797626">grundy数を習得したかった - nanikakaのAOJ航海日誌</a>
</li>
<li>
<a href="https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/">https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/</a>
</li>
</ul>
<p>
今回は、このアルゴリズムにメモ化再帰を適用した.
</p>
解答
[sourcecode language="python" title="" ] MAXN = 200
<p>
vx = [1, -1, 0, 0] vy = [0, 0, 1, -1] memo = [[[-1 for i in range(MAXN)] for j in range(MAXN)] for k in range(MAXN)]
</p>
<p>
class BoardEscapeDiv2: def isWinning(self, s, x, y, move): n = len(s) m = len(s[0])
</p>
<p>
if move == 0: return False if s[x][y] == 'E': return False if memo[x][y][move] != -1: return memo[x][y][move]
</p>
<p>
for i in range(4): nx = x + vx[i] ny = y + vy[i] if nx < 0 or ny < 0 or nx >= n or ny >= m or s[nx][ny] == '#': continue if not self.isWinning(s, nx, ny, move - 1): memo[x][y][move] = True return True
</p>
<p>
memo[x][y][move] = False return False
</p>
<p>
def findWinner(self, s, k): n = len(s) m = len(s[0])
</p>
<p>
for i in range(n): for j in range(m): if s[i][j] == 'T': x = i y = j
</p>
<p>
return "Alice" if self.isWinning(s, x, y, k) else "Bob" [/sourcecode]
</p>
おわりに
本番では解けなかった. こういう問題をさらりととけないと Div1には上がれないのか. 道は遠いな.