Stopping Problem

Time Limit : 1 sec, Memory Limit : 262144 KB

問題 D : 停止問題

G○○gle Code Jam は G○○gle 社が年に 1 度開催するコンテストである. 優勝者は G○○gle への入社を許される,世界最高峰のコンテストだ. しかし勿論,それ以外の参加者は帰らぬ者となる.

G○○gle Code Jam では自分の好きなプログラミング言語や処理系を使うことができる. 僕は Defunge という自らが開発したプログラミング言語で参加することにした. この言語を使えば,計算困難な問題はおろか,判定不能な問題ですら解決できる気がしている.

問題

与えられるプログラムが停止するかを判定するプログラムを作成せよ. 与えられるプログラムは,以下で説明するプログラミング言語 Defunge で記述されている.

Defunge のプログラムの命令は 1 文字であり,1 次元の列ではなく 2 次元の格子状に並んでいる. 下図は,Defunge のプログラムの例である:

6>--v.
.^--_@

Defunge の言語仕様は以下のようになっている.

  • Defunge のプログラムは、左上のマスから右向きで開始する. (左上のマスの命令が最初に実行される.)
  • 命令によって進む向きが上下左右に変更されることがある.
  • 端に達したら反対側の端へジャンプする.
  • メモリは 0 から 15 までの 1 つの整数を記憶することができる.
  • メモリにははじめ 0 が記憶されている.

Defunge の命令は以下の通りである.

  • '<' … 実行の向きを左にする.
  • '>' … 実行の向きを右にする.
  • '^' … 実行の向きを上にする.
  • 'v' … 実行の向きを下にする.
  • '_' … メモリの値が 0 ならば実行の向きを右に,そうでなければ左にする.
  • '|' … メモリの値が 0 ならば実行の向きを下に,そうでなければ上にする.
  • '?' … 実行の向きが上下左右のいずれかにランダムに等確率で変更される.
  • '.' … 何もしない.
  • '@' … プログラムの実行を停止する.
  • '0' - '9' … メモリの値を指定の数値にする.
  • '+' … メモリの値に 1 を加える,ただし値が 15 だった場合 0 にする.
  • '-' … メモリの値から 1 を引く,ただし値が 0 だった場合 15 にする.

入力

入力の最初の行は 2 つの整数 R, C を含む.

続く R 行はプログラムを表す。それぞれ C 文字の文字列を含む。

出力

プログラムが停止する可能性がある場合は YES と出力せよ.

そうでないとき,NO と出力せよ.

制約

  • 1 ≤ R ≤ 20
  • 1 ≤ C ≤ 20

入出力例

入出力例 1

入力例 1:

2 6
6>--v.
.^--_@

入力例 1 に対する出力:

YES

入出力例 2

入力例 2:

2 6
5>--v.
.^--_@

入力例 2 に対する出力:

NO

入出力例 3

入力例 3:

2 6
.>--v.
.^--?@

入力例 3 に対する出力:

YES

補足

Defunge は Befunge と類似している. Befunge の理解は Defunge の理解を助けるかもしれないが, 異なる点も多いため,注意せよ.


Source: University of Tokyo Programming Contest 2011 , Tokyo, Japan, 2011-05-14
Problem Setter:  Takuya Akiba
http://www.utpc.jp/2011/