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, 但也有很多不同之处,因此请注意。