记录编号	192248	评测结果	AAAAAAAAAA
题目名称	2042.贪吃蛇	最终得分	100
用户昵称	四季木哥	是否通过	通过
代码语言	C++	运行时间	0.084 s
提交时间	2015-10-10 08:29:13	内存使用	30.75 MiB

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

int g[22][22][(1<<14)+100];	
int map[22][22];
int l[15],c[15];
int n,m,ans,L,k;
struct State{
	int x,y,s,f;
	bool operator < (const State &rsh) const{ 
		return f>rsh.f; 
	}
};
priority_queue<State> q;

int f(int x,int y,int s){
	int h=x+y-2;
	return h+g[x][y][s];
}

/*void print(int x){
	vector<int> p;
	p.clear();
	for(int i=1;i<=2*L;i++){
		int d=x&1;
		p.push_back(d);
		x>>=1;
	}
	for(int i=p.size()-1;i>=0;i--) cout<<p[i];
	cout<<endl;
}*/


int A_sharp(int x,int y,int s0){
	g[x][y][s0]=0;
	q.push((State){x,y,s0,f(x,y,s0)}); 
	while(!q.empty()){
		State now=q.top();	
		q.pop();
		int s=now.s;
		if(now.x==1&&now.y==1) return g[1][1][s];
		c[0]=now.x,l[0]=now.y;
		int cur=0;
		for(int i=2*L-2;i>=0;i-=2){
			++cur;
			int d=((s>>i)&1)+(((s>>(i+1))&1)<<1);
			if(d==0){
				c[cur]=c[cur-1]-1;
				l[cur]=l[cur-1];
			}
			if(d==1){
				c[cur]=c[cur-1]+1;
				l[cur]=l[cur-1];
			}
			if(d==2){
				c[cur]=c[cur-1];
				l[cur]=l[cur-1]-1;
			}	
			if(d==3){
				c[cur]=c[cur-1];
				l[cur]=l[cur-1]+1;
			}
		}
		for(int i=1;i<=cur;i++) map[c[i]][l[i]]=1;
		State next;
		if(now.x>1&&!map[now.x-1][now.y]&&!g[now.x-1][now.y][(s>>2)|(1<<2*(L-1))]){
			next.s=(s>>2)|(1<<2*(L-1));
			g[now.x-1][now.y][next.s]=g[now.x][now.y][s]+1;
			next.x=now.x-1;
			next.y=now.y;
			next.f=f(next.x,next.y,next.s);
			q.push(next);
		} 
		if(now.x<n&&!map[now.x+1][now.y]&&!g[now.x+1][now.y][(s>>2)]){
			next.s=(s>>2);
			g[now.x+1][now.y][next.s]=g[now.x][now.y][s]+1;	
			next.x=now.x+1;
			next.y=now.y;
			next.f=f(next.x,next.y,next.s);
			q.push(next);
		}	
		if(now.y>1&&!map[now.x][now.y-1]&&!g[now.x][now.y-1][(s>>2)|(3<<2*(L-1))]){
			next.s=(s>>2)|(3<<2*(L-1));
			g[now.x][now.y-1][next.s]=g[now.x][now.y][s]+1;
			next.x=now.x;
			next.y=now.y-1;
			next.f=f(next.x,next.y,next.s);
			q.push(next);
		}
		if(now.y<m&&!map[now.x][now.y+1]&&!g[now.x][now.y+1][(s>>2)|(2<<2*(L-1))]){
			next.s=(s>>2)|(2<<2*(L-1));
			g[now.x][now.y+1][next.s]=g[now.x][now.y][s]+1;
			next.x=now.x;
			next.y=now.y+1;
			next.f=f(next.x,next.y,next.s);
			q.push(next);
		}
		for(int i=1;i<=cur;i++) map[c[i]][l[i]]=0;
	}
}

int main(){
	freopen("snake.in","r",stdin);
	freopen("snake.out","w",stdout);
	cin>>n>>m>>L;
	L--;
	int a,b;
	cin>>a>>b;
	int x=a,y=b,lastx=a,lasty=b;
	int s=0;
	for(int i=1;i<=L;i++){
		cin>>a>>b;
		s<<=2;
		if(a==lastx+1) s|=1;
		if(b==lasty+1) s|=3;
		if(b==lasty-1) s|=2;
		lastx=a;
		lasty=b;
	}
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>a>>b;
		map[a][b]=1;
	}
	ans=A_sharp(x,y,s);
	cout<<ans;
return 0;
}