让我们提醒您一个非常流行的游戏“贪吃蛇”(有时也称为“Boa”、“Python”或“Worm”)的规则。
游戏场地由一个 n × m 的矩形桌子表示。场地的某些方格被认为是无法通过的(墙),而场地的所有其他方格都是可通行的。
你控制一条蛇,蛇由分段组成。每个线段恰好占据场地的一个可通过的方格,但任何可通行的方格最多包含一个线段。所有段均由从 1 到 k 的整数索引,其中 k 是蛇的长度。第 1 段是头部,第 k 段是尾部。对于任意 i (1 ≤ i < k),索引为 i 和 i + 1 的线段位于域的相邻方格中,即这些方格共享公共边。
其中一个可通行的田野方块包含一个苹果。蛇的目标是到达苹果并吃掉它(即将其头部置于与苹果成正方形的位置)。
蛇在整个游戏中移动。在一次移动过程中,蛇可以将其头部移动到相邻的方格。所有其他部分都跟随头部。也就是说,每个段号 i (1 < i ≤ k) 移动到刚刚有段号 i - 1 的方格。考虑包括头部在内的所有段同时移动(参见第二个测试示例)。如果蛇的头移动到无法通过的方格或移动到被其其他部分占据的方格,则蛇死亡。这就是为什么我们会认为此类举动无效。
你的任务是确定蛇到达苹果所需的最小有效移动次数。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 15) — 游戏场的行数和列数。
接下来的 n 行描述了游戏领域。每行包含 m 个字符。字符“#”代表墙,“.”是一个尚可的正方形,“@”是一个苹果。蛇的第一段由字符“1”表示,第二段由字符“2”表示,依此类推。
游戏字段描述不包含除“#”、“.”、“@”和数字(0除外)之外的任何字符。保证描述的字段正确。保证描述的字段恰好包含一个苹果和一条蛇,蛇的长度至少为3,最多为9。
输出
在输出中打印一个整数——到达苹果所需的最小移动次数。如果蛇无法到达苹果,则打印 -1。
示例
输入 #1
4 5 ##... ..1#@ 432#. ...#.
输出 #1
4
输入 #2
4 4 #78# .612 .543 ..@.
输出 #2
6
输入 #3
3 2 3@ 2# 1#
输出 #3
-1