记录编号	8395	评测结果	AAAAAAAAAAAAA
题目名称	[BYVoid S3] 潜入辛迪加	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.089 s
提交时间	2008-11-13 21:10:55	内存使用	205.93 MiB

#include <iostream>

#define MAXN 55
#define INF 99999999
#define MAXLONG 1000000

using namespace std;

typedef struct{
	int x;
	int y;
	int key;
	int deep;
}Que;

const int Dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,ans,map[MAXN][MAXN];
bool hash_sta[66000][MAXN][MAXN];
Que que[MAXLONG];

inline bool judge(Que new_sta)
{
	if (hash_sta[new_sta.key][new_sta.x][new_sta.y])
		return false;
	return true;
}

inline void makekey(int &key,int x)
{
	if ( (  key & (1<<(x-1)) )!=(1<<(x-1)))
		key+=1<<(x-1);
}
inline bool ifkey(int key,int x)
{
	if ( (  key & (1<<(x-1)) )==(1<<(x-1)))
		return true;
	return false;
}

void bfs()
{
	int head=-1,tail=0,d,x,y;
	Que sta,new_sta;
	que[0].x=que[0].y=1;
	que[0].deep=0;
	que[0].key=0;
	hash_sta[0][1][1]=true;
	//deep不能用来判重!!!
	while (head<tail)
	{
		sta=que[++head];
		for (d=0;d<4;d++)
		{
			x=sta.x+Dir[d][0];
			y=sta.y+Dir[d][1];
			if (!(x>=1 && x<=n && y>=1 && y<=n))
				continue;
			if (map[x][y]==-1)
				continue;
			if (map[x][y]==0)
			{
				new_sta.x=x;
				new_sta.y=y;
				new_sta.deep=sta.deep+1;
				new_sta.key=sta.key;
			}
			if (map[x][y]>=1 && map[x][y]<=m)
			{
				new_sta.x=x;
				new_sta.y=y;
				new_sta.deep=sta.deep+1;
				new_sta.key=sta.key;
				makekey(new_sta.key,map[x][y]);
			}
			if (map[x][y]>m)
			{
				if (ifkey(sta.key,map[x][y]-m))
				{
					new_sta.x=x;
					new_sta.y=y;
					new_sta.deep=sta.deep+1;
					new_sta.key=sta.key;
				}
				else
					continue;
			}
			if (judge(new_sta))
			{
				que[++tail]=new_sta;
				hash_sta[new_sta.key][new_sta.x][new_sta.y]=true;
				if (new_sta.x==n && new_sta.y==n)
				{
					ans=new_sta.deep;
					return;
				}
			}
		}
	}
}

void run()
{
	ans=INF;
	bfs();
}

void ini()
{
	int i,j,a,x,y,d;
	cin>>n>>m;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			scanf("%d",&a);
			if (a==-1)
				map[i][j]=a;
			if (a==-2)
			{
				map[i][j]=-1;
				for (d=0;d<4;d++)
				{
					x=i+Dir[d][0];
					y=j+Dir[d][1];
					if (x>=1 && x<=n && y>=1 && y<=n)
					{
						map[x][y]=-1;
					}
				}
			}
			if (a>=0)
			{
				if (map[i][j]!=-1)
					map[i][j]=a;
			}

		}
}

int main()
{
	freopen("syndicate.in","r",stdin);
	freopen("syndicate.out","w",stdout);
	ini();
	run();
	printf("%d",ans);
	return 0;
}