← 返回题目列表

AtCoder · utpc2011_4

D. 停止问题

中文机器翻译题面 查看原题

G○○gle Code Jam 是由 G○○gle 公司每年举办一次的竞赛。 优胜者将被允许加入 G○○gle,这是世界顶级竞赛。 但是当然,其他参加者将成为无法返回的人。

在 G○○gle Code Jam 中,你可以使用自己喜欢的编程语言或执行环境。我决定使用我自己开发的编程语言 Defunge 参加。如果使用这种语言,我感觉即使是计算困难的问题,甚至是不可判定的问题也能解决。

問題

请创建一个程序,用来判定给定程序是否会停止。给定的程序是用下面所述的编程语言 Defunge 编写的。

Defunge 的程序指令为 1 个字符,并且不是一维列,而是排列在二维网格中。下图是 Defunge 程序的示例:

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

Defunge 的语言规范如下。

  • Defunge 程序从左上角的格子开始向右执行。(左上角格子的指令最先执行。)
  • 命令可能会改变前进的方向,上下左右。
  • 到达边缘时,会跳到对面的边缘。
  • 内存可以存储从 0 到 15 的一个整数。
  • 内存初始值为 0。

Defunge 的命令如下。

  • '<' … 将执行方向设为左。
  • '>' … 将执行方向设为右。
  • '^' … 将执行方向设为上。
  • 'v' … 将执行方向设为下。
  • '_' … 如果内存的值为 0,则将执行方向设为右,否则设为左。
  • '|' … 如果内存的值为 0,则将执行方向设为下,否则设为上。
  • '?' … 执行方向以上下左右中的任意方向随机且等概率改变。
  • '.' … 什么也不做。
  • '@' … 停止程序的执行。
  • '0' - '9' … 将内存的值设定为指定的数字。
  • '+' … 内存的值加 1,但如果值为 15 则变为 0。
  • '-' … 内存的值减 1,但如果值为 0 则变为 15。

入力

输入的第一行包含两个整数 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, 但也有很多不同之处,因此请注意。