记录编号	307523	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-09-15 14:35:18	内存使用	1.32 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#define LL long long
using namespace std;
const int maxn=1010;
const int dx[5]={0,0,1,-1};
const int dy[5]={1,-1,0,0};
struct Node{
	int x,y,type,step;
	Node(){};
	Node(int a,int b,int c,int d){x=a;y=b;type=c;step=d;}
};
queue<Node> q;
bool vis[16][16][2055];
int a[19][19][19][19],hav[16][16][10];
int ans=0x7f7f7f7f;
void Init();
int n,m,p,K;
void Bfs(){
	//if(hav[1][1]!=0)
	//q.push(Node(1,1,(1<<(hav[1][1]-1)),0));
	q.push(Node(1,1,0,0));
	while(!q.empty()){
		Node temp=q.front();q.pop();
		int x=temp.x,y=temp.y;
		//if(temp.step==36)printf("%d %d \n",x,y);
		if(x==n && y==m){
			//printf("%d %d %d %d\n",x,y,temp.type,temp.step);
			ans=min(temp.step,ans);
		}
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i],type=temp.type;
			if(xx<1 || yy<1 || xx>n || yy>m || a[x][y][xx][yy]==-1)continue;
			if(a[x][y][xx][yy]){
				int k=a[x][y][xx][yy]-1;
				if((type&(1<<k))==0)continue;
			}
			if(hav[xx][yy]){
				//if(x==3 && y==2 && temp.type==2 && temp.step==7)printf("<<%d %d %d>>\n",xx,yy,type);
				//if(xx==2 && yy==1 && temp.step==0)printf("%d\n",type & (1<<(hav[xx][yy]-1))); 
				int zhi=1;
				while(hav[xx][yy][zhi]){
					type|=(1<<(hav[xx][yy][zhi]-1));zhi++;
				}
				//if(x==3 && y==2 && temp.type==2 && temp.step==7)printf("<<%d %d %d>>\n",xx,yy,type);
			}
			if(vis[xx][yy][type])continue;
			vis[xx][yy][type]=1;
			q.push(Node(xx,yy,type,temp.step+1));
		}
	}
}
int main(){
    freopen("rescue.in","r",stdin);freopen("rescue.out","w",stdout);
    Init();
    //system("pause");
    return 0;
}
void Init(){
	scanf("%d%d%d%d",&n,&m,&p,&K);
	for(int i=1;i<=K;i++){
		int x1,y1,x2,y2,type;
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&type);
		if(type==0)a[x1][y1][x2][y2]=a[x2][y2][x1][y1]=-1;
		else a[x1][y1][x2][y2]=a[x2][y2][x1][y1]=type;
	}
	int L;scanf("%d",&L);
	for(int i=1;i<=L;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		int zhi=1;
		while(hav[x][y][zhi])zhi++;
		hav[x][y][zhi]=z;
		//printf("a[%d][%d][%d]=%d\n",x,y,zhi,a[x][y][zhi]);
	}
	Bfs();
	if(ans==0x7f7f7f7f)printf("-1\n");
	else printf("%d\n",ans);
}