AT_maximum_2013_i 実績: ヘビマスター

[problemUrl]: https://atcoder.jp/contests/maximum-cup-2013/tasks/maximum_2013_i あなたはヘビゲームをプレイしている。 プレイヤーはヘビを操作し、その頭がマップの壁あるいは自身の身体にぶつからないようにしながら、ランダムで出現するエサを回収する。 エサを回収するたびにヘビの身体は 1 マスずつ長くなっていく、というゲームである。 あなたがプレイしているヘビゲームには実績という機能あり、ゲーム中に特定の行動を取るとその行動に対応した実績を獲得できる。 あなたが獲得しようとしている実績の条件は、マップ内の移動可能なすべてのマスを一筆書きのように通過する、というものである。 長さ $ L $ のヘビは $ L $ 個の連接するマスからなり、マス 1 つがヘビの体の節 1 つを表している。 ヘビの体節には 1 から $ L $ までの番号が付いており、番号順にヘビの頭からヘビの尻尾までを表す。 ヘビの $ i $ 番目の体節と $ i\ -\ 1 $ 番目の体節は隣り合ったマスに存在する ($ i\ =\ 2..L $)。 2 つのマスが隣り合っているとは、2 つのマスが共有する辺をもつということである。 ヘビは進行方向に対して前、右、左の 3 方向いずれかに 1 マスずつ移動することができる。 ヘビの進行方向は、ヘビの 2 番目の体節から見て 1 番目の体節 (ヘビの頭) がある方向である。 ヘビが移動するとき、ヘビの体はヘビの頭が通った経路を追従するように移動する。 すなわち、ヘビの頭が 1 マス移動するとき、それに合わせて $ i $ 番目の体節は $ i\ -\ 1 $ 番目の体節の位置へ移動する ($ i\ =\ 2..L $)。 この挑戦の間エサは出現しないので、ヘビの長さはスタート時から変化しない。 ヘビの長さとマップが与えられたとき、ヘビの頭がマップの壁あるいは自身の身体にぶつからないようにしながら、通行可能なすべてのマスをそれぞれちょうど 1 度ずつまわることができるか判定するプログラムを作成したい。 入力は複数のデータセットからなり、入力の終わりはスペースで区切られた 3 つのゼロからなる。各データセットは以下のように構成される。 > $ L $ $ H $ $ W $ $ m(1,\ 1) $ $ m(1,\ 2) $ ... $ m(1,\ w) $ $ m(2,\ 1) $ $ m(2,\ 2) $ ... $ m(2,\ w) $ : $ m(h,\ 1) $ $ m(h,\ 2) $ ... $ m(h,\ w) $ $ L $ はヘビの長さ、$ H $ と $ W $ はマップの行および列の数を表す整数である。 これらは $ 2\ ≦\ L\ ≦\ 9 $, $ 1\ ≦\ H,\ W\ ≦\ 8 $ を満たす。 続く $ H $ 行にマップの状態が与えられる。各マスの状態は 1 つの半角文字で表され、それぞれ以下の意味をもつ。 - `#`: 壁 (通行不可) - `.`: 何もない (通行可) - `1`..`9`: 開始時点のヘビの位置 (通行可) `1` のマスは通過済み、それ以外の数字のマスは未通過とする。 なお、マップの最も外側のマスはすべて壁であることがわかっている。 各データセットについて、すべてのマスをまわることができるならば `Yes` を、そうでないならば `No` をそれぞれ 1 行に出力せよ。 ``` 2 5 4 #### #12# #..# #..# #### 2 5 4 #### #12# #.## #..# #### 8 7 7 ####### #...#.# #1#.#.# #2..#.# #3###.# #45678# ####### 9 7 7 ####### #...#.# #1#.#.# #2..#.# #3###9# #45678# ####### 0 0 0 ``` ``` Yes No Yes No ``` - 1 セット目について、「下下右上上」と移動するとすべてのマスをまわれる。 - 2 セット目について、「下下右」と移動すると右上のマスに辿りつけない。 - 3 セット目について、「上右右下下左左下下右右右右上上上上」と移動するとすべてのマスをまわれる。 - 4 セット目について、「上右右下下左左」と移動すると、7 回目の移動のとき 1 番目の体節と 9 番目の体節が衝突してしまう。

N/A

N/A