← 返回题目列表

AtCoder · maximum_2013_i

I. 成就:蛇大师

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

問題

您正在玩贪吃蛇游戏。 玩家控制蛇收集随机出现的食物,同时避免蛇的头部与地图的墙壁或自己的身体碰撞。 在这个游戏中,蛇每次收集食物,身体都会变长一格。

您正在玩的贪吃蛇游戏有一个称为成就的功能,如果您在游戏过程中执行特定操作,您就可以获得与该操作相对应的成就。 你想要获得的成就的条件是一举穿过地图上所有可移动的方格。

长度为 L 蛇是 它由 L 连接的方块组成,每个方块代表蛇身体的一部分。 蛇的身体部分从1开始 它们编号到 L ,代表从蛇头到蛇尾的数字。 蛇的 i 第身体部分和 第 i - 1 身体片段存在于相邻的方块中 (i = 2..L)。 如果两个正方形有公共边,则它们是相邻的。

蛇可以在三个方向上各移动一格:向前、向右或向左。 蛇的行进方向是其第一身体部分(蛇的头部)相对于其第二身体部分的方向。

当蛇移动时,它的身体会沿着蛇头所走的路径移动。 换句话说,当蛇头移动一格时, 第 i 身体部分是 i - 1 移动到正文段的位置 (i = 2..L)。

由于本次挑战期间没有食物出现,因此蛇的长度从一开始就不会改变。 给定蛇和地图的长度,我想编写一个程序来确定蛇的头是否可以精确地绕每个可通过的方格一次,而不会撞到地图的墙壁或它自己的身体。


入力

输入由多个数据集组成,输入以空格分隔的三个零结尾。每个数据集的结构如下。

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..9:开始时的蛇位置(可通过) 带有

1 的方格已通过,带有其他数字的方格尚未通过。

众所周知,地图上所有最外面的方块都是墙。

出力

对于每个数据集,如果你可以绕过所有的方块 Yes ,否则 将每个 No 打印在一行上。


入力例

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 和第 9 身体部分将在第 7 次移动时发生碰撞。