CF225D Snake

让我们来回顾一下一个非常流行的游戏——“贪吃蛇”（有时也称为“Boa”、“Python”或“Worm”）的规则。 游戏场地用一个 $n \times m$ 的矩形棋盘表示。棋盘上的某些格子被认为是不可通过的（墙），其余格子是可以通过的。 你控制一条蛇，蛇由若干节组成。每一节蛇身正好占据一个可以通过的格子，且每个可通过的格子最多只被一节蛇身占据。所有蛇身按 $1$ 到 $k$ 编号，$k$ 表示蛇的长度。第 $1$ 节是蛇头，第 $k$ 节是蛇尾。对于任意 $i$（$1 \leq i < k$），第 $i$ 节和第 $i + 1$ 节必须处于相邻的格子上，即这两个格子有公共边。 一个可通过的格子上有一个苹果。蛇的目标是到达该格子并吃掉苹果（即蛇头所在位置与苹果相同）。 游戏中，蛇会移动。每移动一次，蛇头可以移动到一个相邻的格子。其它蛇身则依次跟随蛇头移动。具体来说，第 $i$ 节（$1 < i \leq k$）会移动到刚才第 $i-1$ 节的位置。可以认为，所有蛇节（包括蛇头）是同时移动的（见样例二）。如果蛇头移动到了不可通过的格子、或者移动到了被蛇自己的其它节占据的格子，那么蛇就会死亡。这样的移动我们都认为是非法的。 你的任务是判断，蛇最少需要多少次合法移动才能到达苹果所在的格子。

第一行包含两个用空格分隔的整数 $n$ 和 $m$（$1 \leq n,m \leq 15$），表示游戏场地的行数和列数。 接下来的 $n$ 行描述了游戏场地。每行包含 $m$ 个字符。其中“#”表示墙，“.”表示可通过的格子，“@”表示苹果。蛇的第 $1$ 节用字符“1”表示，第 $2$ 节用“2”表示，依此类推。 输入中不会出现除“#”、“.”、“@”以及（非 $0$）数字以外的其他字符。保证输入的场地描述是合法的。保证恰好有一个苹果和一条蛇，蛇的长度不少于 $3$ 且不超过 $9$。

输出一个整数，表示蛇到达苹果所需的最小合法移动次数。如果无法到达苹果，请输出 $-1$。

由 ChatGPT 5 翻译