相信大家都玩过贪吃蛇游戏吧。
在n×m的迷宫中，有着一条长度不超过9的贪吃蛇，它已经将所有的食物吃光了，现在的目标是移动到出口。
它走的时候不能碰到自己的身体，也不能碰到墙壁。(如果贪吃蛇的长度>3并且下一步要走到自己的尾部，是合法的)
问它能不能走到出口，如果能，最少要移动几步？
Input
数据包含多组数据，请读入到文件末尾EOF
每组数据第一行包含两个整数n,m(1≤n,m≤15)代表迷宫的大小。
接下来n行，每行包含一个长度为m的字符串，来表示迷宫。
字符串中仅包含.、#、@、1 ~ 9、.代表空地 # 代表墙 数字一定是1∼k 连续的k个数字，代表贪吃蛇，1代表它的头，k代表它的尾，数据保证数字i一定和数字i+1在迷宫中相邻。 @ 代表出口。
Output
对于每组数据，先输出Case #i: ,i为当前数据组数。
接下来一个数，代表贪吃蛇最少需要移动的步数，若无法移动出去输出-1
解题报告
主要是判重问题
肯定不能vis[15][15].....x9
内存依然爆炸，其实大部分都是没有使用的,因此我们考虑到
蛇的每截身体较于前面一截只有 4 种状态，我们用4进制来压缩蛇的身体,这样就能存下了，注意蛇头可以移动到最后一截身体所在的位置.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Max = ;
char G[Max+][Max+];
bool vis[][][];
int R,C,targetx,targety,n;
// n is snake-body num
int dir[][] ={-,,,,,-,,};
int caculate[] ={,,,,,,,};
typedef struct status
{
int x[];
int y[];
int step;
}; status ori;
status thisq[]; int getturn(int x,int y,int x0,int y0){
if (x - x0 == ) return ;
if (x - x0 == -) return ;
if (y - y0 == ) return ;
if (y - y0 == -) return ;
printf("Error at get turn!\n");
} int getcode(status& x){
int buffer[];
int code = ;
for(int i = ;i<n;++i)
code += getturn(x.x[i],x.y[i],x.x[i-],x.y[i-]) * caculate[i-];
return code;
} bool judge(status& x){
int tx = x.x[];
int ty = x.y[];
for(int i = ;i<n;++i)
if(x.x[i] == tx && x.y[i] == ty)
return false;
return true;
} bool dfs1(int x,int y){
int front = ,rear = ;
int q[][];
bool evis[][];
memset(evis,false,sizeof(evis));
evis[x][y] = true;
q[rear][] = x;
q[rear++][] = y;
while(front < rear)
{
int tx = q[front][];
int ty = q[front++][];
if (tx == targetx && ty == targety) return true;
for(int i = ;i<;++i)
{
int newx = tx + dir[i][];
int newy = ty + dir[i][];
if (!evis[newx][newy] && G[newx][newy] != '#' && newx < R && newx >= && newy < C && newy >=)
{
q[rear][] = newx;
q[rear++][] = newy;
evis[newx][newy] = true;
}
}
} return false;
} int dfs(){
int front = ,rear = ;
ori.step = ;
thisq[rear++] = ori;
vis[ori.x[]][ori.y[]][getcode(ori)] = true;
while(front < rear)
{
int tx = thisq[front].x[];
int ty = thisq[front].y[];
int step = thisq[front].step;
if (tx == targetx && ty == targety) return step;
for(int i = ;i < ;++i)
{
int newx = tx + dir[i][];
int newy = ty + dir[i][];
int newstep = step+;
if (newx >= R || newx < || newy >=C || newy < || G[newx][newy] == '#')
continue;
status newst;
newst.x[] = newx;
newst.y[] = newy;
newst.step = step + ;
for(int j=;j<n;++j)
{
newst.x[j] = thisq[front].x[j-];
newst.y[j] = thisq[front].y[j-];
}
if (!vis[newst.x[]][newst.y[]][getcode(newst)] && judge(newst))
{
thisq[rear++] = newst;
vis[newst.x[]][newst.y[]][getcode(newst)] = true;
}
} front++;
} return -;
} bool input(){
while(scanf("%d%d%*c",&R,&C)==)
{
n = ;
memset(vis,false,sizeof(vis));
for(int i = ;i<R;++i)
gets(&G[i][]);
for(int i = ;i<R;++i)
for(int j = ;j<C;++j)
if(G[i][j] == '@')
{
targetx = i;
targety = j;
}
else if(G[i][j] <= '' && G[i][j] >= '')
{
ori.x[G[i][j] - ''] = i;
ori.y[G[i][j] - ''] = j;
n ++ ;
}
return true;
}
return false;
} int main(int argc,char * argv[]){
int T = ;
while(input() == true)
{
if(!dfs1(ori.x[],ori.y[]))
{
cout << "Case #"<< T++ <<": -1" <<endl;
continue;
}
int ans = dfs();
cout << "Case #"<< T++ <<": "<< ans <<endl;
}
return ;
}