题目描述

贪吃蛇是一款经典电子游戏。游戏目标是控制蛇头移动到苹果所在位置。蛇吃到苹果后会变长，然后出现新的苹果。

游戏在一个网格上进行，蛇身体的每一节占据一个格子。蛇头每一步可以向三个方向之一移动，但不能反向移动。蛇身会跟随蛇头移动。

蛇头不能撞到身体，也不能走出网格。由于整条蛇同时移动，因此蛇头允许进入蛇尾当前所在、但本步即将离开的格子。

给定一个局面，请判断蛇头是否能够到达苹果。如果不能，则蛇注定会死亡。

输入格式

第一行包含两个整数 $r,c$，表示网格有 $r$ 行 $c$ 列。

接下来 $r$ 行，每行包含长度恰好为 $c$ 的字符串。字符集合为：

., 0, 1, ..., 9, a, ..., f, A

含义如下：

• . 表示空格；
• A 表示苹果；
• 十六进制字符 0 到 9、a 到 f 表示蛇身，其中 0 是蛇头，后续字符依次表示身体各节。

蛇的长度在 $1$ 到 $16$ 之间。蛇身字符严格连续，不能跳号，即若存在某一节，则之前编号的所有节都存在。

保证：

• 每个蛇身字符最多出现一次；
• 除 0 外，每一节都与前一节相邻；
• 网格中恰好有一个苹果。

输出格式

如果蛇头能够到达苹果，输出：

1

否则输出：

0

样例 #1

输入 #1

5 8
......01
....98.2
...A.7.3
.....654
........

输出 #1

1

样例 #2

输入 #2

5 4
...A
....
6789
5432
..01

输出 #2

0

样例 #3

输入 #3

5 5
....A
.....
678..
54321
....0

输出 #3

1

样例 #4

输入 #4

4 4
567A
4389
12ba
0dc.

输出 #4

1