记录编号	187967	评测结果	AAAAAAAAAA
题目名称	2042.贪吃蛇	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.086 s
提交时间	2015-09-21 16:23:43	内存使用	7.88 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,L,q,ans;
struct rec{int x,y;}a[10];
struct red{int x,y,k,step,cm;};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dz[]={0,1,2,3};
bool f[22][22][16400];
bool map[22][22];
bool mpp[22][22];

int check(int x,int y,int k,int i)
{
	int tx,ty,rx=x,ry=y;
	tx=x+dx[i],ty=y+dy[i];
	if(tx<=0 ||ty<=0 || tx>=n+1 || ty>=m+1) return -1;
	memcpy(mpp,map,sizeof map);
	for(int temp,j=2;j<=L;j++)
	{
		temp=3&(k>>(j-2)*2);
		rx=rx-dx[temp];
		ry=ry-dy[temp];
		mpp[rx][ry]=1;
	}
	if(mpp[tx][ty]) return -1;
	k=k&((1<<(L-2)*2)-1);
	k<<=2;
	k+=dz[i];
	return k;
}

bool operator <(red x,red y){	return x.cm<y.cm;}

void bfs(red head)
{
	red p;
	priority_queue<red>q;
	q.push(head);
	f[head.x][head.y][head.k]=1;
	while(q.size())
	{
		head=q.top();q.pop();
		for(int temp,i=0;i<=3;i++)
			if(temp=check(head.x,head.y,head.k,i),temp!=-1)
			{
				p.x=head.x+dx[i];p.y=head.y+dy[i];p.k=temp;p.step=head.step+1;
				p.cm=-p.step+2-p.x-p.y;
				if(p.x==1 && p.y==1) {ans=p.step;return;}
				if(!f[p.x][p.y][p.k])
					f[p.x][p.y][p.k]=1,q.push(p);
			}
	}
}

int main()
{
	freopen("snake.in","r",stdin);
	freopen("snake.out","w",stdout);
	scanf("%d%d%d",&n,&m,&L);
	int temp=0;
	ans=1<<30;
	for(int i=1;i<=L;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		if(i!=1)for(int j=0;j<=3;j++)
			if(dx[j]+a[i].x==a[i-1].x && dy[j]+a[i].y==a[i-1].y)
			{
				temp+=dz[j]<<(2*i-4);
				break;
			}
	}
	cin>>q;
	for(int x,y,i=1;i<=q;i++) scanf("%d%d",&x,&y),map[x][y]=1;
	if(a[1].x==1 && a[1].y==1) {printf("0\n");return 0;}
	red tt;
	tt.x=a[1].x,tt.y=a[1].y,tt.k=temp,tt.step=0,tt.cm=2-a[1].x-a[1].y;
	bfs(tt);
	printf("%d\n",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}