记录编号	192897	评测结果	AAAAAAAAAA
题目名称	2042.贪吃蛇	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.728 s
提交时间	2015-10-13 11:37:27	内存使用	48.00 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

int n, m, l, cnt, del[25][25];
int movx[5] = {0, 1, -1}, movy[5] = {0, 0, 0, 1, -1};
int mul[8] = {1, 5, 25, 125, 625, 3125, 15625, 78125};
bool vis[25][25][80005]; 

struct node{
	int x, y, zt, g, h;
	node()
	{
		x = y = zt = g = h = 0;
	}
	bool operator < (node tmp) const
	{
		return h + g > tmp.h + tmp.g;
	}
};

priority_queue <node> q;

bool ok(int x, int y, node t)
{
	if(del[x][y] || x < 1 || x > n || y < 1 || y > m) return 0;
	int tx = t.x, ty = t.y;
	for(int i = 1; i < l; i++, t.zt /= 5)
	{
		if(t.zt % 5 == 1) tx--;
		if(t.zt % 5 == 2) tx++;
		if(t.zt % 5 == 3) ty--;
		if(t.zt % 5 == 4) ty++;
		if(x == tx && y == ty) return 0;
	}
	return 1;
}

int main()
{
	freopen("snake.in", "r", stdin);
	freopen("snake.out", "w", stdout);
	scanf("%d %d %d", &n, &m, &l);
	{
		node beg;
		scanf("%d %d", &beg.x, &beg.y);
		for(int i = 1, j = 1, lx = beg.x, ly = beg.y; i < l; i++, j *= 5)     // 1 U 2 D 3 L 4 R
		{
			int x, y; scanf("%d %d", &x, &y);
			if(x == lx)
			{
				if(y > ly) beg.zt += j*4;
				if(y < ly) beg.zt += j*3; 
			}
			if(y == ly)
			{
				if(x > lx) beg.zt += j*2;
				if(x < lx) beg.zt += j*1;
			}
			lx = x, ly = y;
		}
		int num; scanf("%d", &num);
		for(int i = 1; i <= num; i++)
		{
			int x, y; scanf("%d %d", &x, &y);
			del[x][y] = 1;
		}
		
		memset(vis, 0, sizeof vis);
		while(!q.empty()) q.pop();
		q.push(beg);
		bool flag = 0;
		while(!q.empty())
		{
			node t = q.top(); q.pop(); 
			if(vis[t.x][t.y][t.zt]) continue;
			if(t.x == 1 && t.y == 1)
			{
				printf("%d\n", t.g);
				flag = 1; break;
			}
			vis[t.x][t.y][t.zt] = 1;
			
			node nx;
			for(int i = 1; i <= 4; i++)
			{
				nx = t; nx.x += movx[i], nx.y += movy[i];
				if(!ok(nx.x, nx.y, t)) continue;
				nx.zt = (nx.zt % mul[l-1]) * 5 + i;
				nx.h = nx.x + nx.y - 2;
				nx.g = t.g + 1;
				if(!vis[nx.x][nx.y][nx.zt])q.push(nx); 
			}
		}
		if(!flag) printf("-1\n");
	}
	return 0;
}