CF225D.Snake

Let us remind you the rules of a very popular game called "Snake" (or sometimes "Boa", "Python" or "Worm").

The game field is represented by an n × m rectangular table. Some squares of the field are considered impassable (walls), all other squares of the fields are passable.

You control a snake, the snake consists of segments. Each segment takes up exactly one passable square of the field, but any passable square contains at most one segment. All segments are indexed by integers from 1 to k, where k is the snake's length. The 1-th segment is the head and the k-th segment is the tail. For any i (1 ≤ i < k), segments with indexes i and i + 1 are located in the adjacent squares of the field, that is, these squares share a common side.

One of the passable field squares contains an apple. The snake's aim is to reach the apple and eat it (that is, to position its head in the square with the apple).

The snake moves throughout the game. During one move the snake can move its head to an adjacent field square. All other segments follow the head. That is, each segment number i (1 < i ≤ k) moves to the square that has just had segment number i - 1. Consider that all segments including the head move simultaneously (see the second test sample). If the snake's head moves to an unpassable square or to the square, occupied by its other segment, the snake dies. That's why we will consider such moves unvalid.

Your task is to determine the minimum number of valid moves that the snake needs to reach the apple.

我们来回顾一下一款非常流行的游戏——“贪吃蛇”（有时也称作“蟒蛇”、“Python”或“蠕虫”）的规则。

游戏场地是一个 $n \times m$ 的矩形表格。场地中某些方格被视为不可通行（即墙壁），其余所有方格均可通行。

你控制一条蛇，该蛇由若干节组成。每一节恰好占据一个可通行方格，但任意一个可通行方格至多被一节占据。所有节均用整数编号，编号从 $1$ 到 $k$，其中 $k$ 为蛇的长度。第 $1$ 节为蛇头，第 $k$ 节为蛇尾。对任意 $i$（满足 $1 \le i < k$），编号为 $i$ 和 $i+1$ 的两节所处的方格必须相邻（即共享一条公共边）。

场地中某一个可通行方格内有一个苹果。蛇的目标是抵达该苹果并将其吃掉（即让蛇头移动到有苹果的方格中）。

蛇在游戏过程中持续移动。每次移动时，蛇头可移向一个相邻的方格。其余所有节则跟随蛇头移动：即对每个 $i$（满足 $1 < i \le k$），第 $i$ 节会移动到原先第 $i-1$ 节所在的方格。注意：所有节（包括蛇头）是同时移动的（参见第二个测试样例）。若蛇头移动到了不可通行的方格，或移动到了被蛇自身其他节所占据的方格，则蛇死亡。因此，我们将这类移动视为非法移动。

你的任务是求出蛇到达苹果所需的最少合法移动次数。

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 15) — the number of rows and columns of the game field.

Next n lines describe the game field. Each of these lines contains m characters. Character "#" represents a wall, "." is a passable square, "@" is an apple. The snake's first segment is represented by character "1", the second one segment — by character "2" and so on.

The game field description doesn't contain any characters besides "#', ".", "@" and digits (except 0). It is guaranteed that the described field is correct. It is guaranteed that the described field contains exactly one apple and exactly one snake, the snake's length is at least 3 and at most 9.

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 15$）—— 分别表示游戏场地的行数和列数。

接下来的 $n$ 行描述游戏场地。每行包含 $m$ 个字符。字符 # 表示墙壁，. 表示可通过的方格，@ 表示苹果。蛇的第一节用字符 1 表示，第二节用字符 2 表示，依此类推。

游戏场地描述中不包含除 #、.、@ 和数字（除 0 外）以外的任何其他字符。保证所描述的场地是合法的。保证所描述的场地中恰好包含一个苹果和一条蛇，且该蛇的长度至少为 $3$，至多为 $9$。

Print a single integer to the output — the minimum number of moves needed to reach the apple. If the snake can't reach the apple, print -1.

向输出打印一个整数——到达苹果所需的最少移动次数。如果蛇无法到达苹果，则打印 $-1$。