题意简述
在一个 $N\times M$ 的矩形方格地图中，有一条长度为 $L$ 的贪吃蛇。
地图的 (1,1) 位置是一个出口，如果贪吃蛇能移动到出口，输出最短步数（头到达出口的步数）；否则输出 -1。
贪吃蛇的移动规则：
- 只能朝边相邻的格子移动
- 不能朝障碍物移动（身体及四周墙壁都视作障碍物）
数据范围： $1\leqslant N, M\leqslant 8$，$2\leqslant L\leqslant 8$。
题目简析
为方便叙述，对贪吃蛇的身体进行编号：蛇头为 -1 号，蛇尾为 $L-2$ 号，以此类推。
因为贪吃蛇的身体是紧邻的。所以，当我们确定了蛇头的位置，对于身体的其它任一部分 $i$，
我们仅需知道 $i$ 相对与 $i-1$ 的方向即可。
则可用链表的思想来存储贪吃蛇：
- 蛇头用一个二元组 $(x,y)$ 表示其位置
- 身体其它部分 $i$ 用一个整数 $dir(i)\in\lbrace 0, 1, 2, 3 \rbrace$ 来表示它相对 $i-1$ 的方向。
注意到方向只有 4 个数，其蛇的身体 $L\leqslant 8$。不难想到状态压缩。
约定 $2^{i},2^{i+1}$ 的系数表示 $i$ 号身体相对于 $i-1$ 号身体的方向。
我们会方向，当蛇头朝某一合法位置移动后，$newdir(i)=dir(i-1)$！
其中，$newdir(i)$ 表示移动后，$i$ 号身体相对于 $i-1$ 号身体的方向。
为什么呢？
因为当贪吃蛇移动一步后，除了蛇头，$i$ 号身体将会移至原先 $i-1$ 号身体所在的地方。
特别地，$newdir(0)$ 将会等于蛇头移动的反方向。
所以，当贪吃蛇移动一步后，我们仅需将方向变量：左移两位，再右移两位，再或上蛇头移动的方向。
剩下的问题就很普通了,搜索即可。
复杂度分析
由于移动操作仅需 $O(1)$ 就可以完成了；但是，判断下一步是否为蛇的身体将需要 $O(L)$ 的时间完成。
一共有 $O(N\times M\times 2^{2L-2})$ 个状态。
空间复杂度$O(N\times M\times 2^{2L-2})$时间复杂度$O(N\times M\times L\times 2^{2L-2})$
Hint
问题的难点在于移动操作的处理。
