记录编号	432761	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2017-08-03 19:22:19	内存使用	35.72 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,p,a[16][16][1<<10],k,s,b[16][16],door[16][16][5],c[16][16][1<<10],h,mov[5][2];//1上2下3左4右
struct ghb{
	int x,y,now;
}e[5000000];
queue<int>S;
int main()
{
	freopen("rescue.in","r",stdin);
	freopen("rescue.out","w",stdout);
//	freopen("1.txt","r",stdin);
	mov[1][0]=0;
	mov[1][1]=1;
	mov[2][0]=0;
	mov[2][1]=-1;
	mov[3][0]=-1;
	mov[3][1]=0;
	mov[4][0]=1;
	mov[4][1]=0;
	scanf("%d%d%d%d",&n,&m,&p,&k);
	memset(a,-1,sizeof(a));
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	for(int o=0;o<(1<<p);o++){
		a[i][j][o]=0;
		c[i][j][o]=++h;
		e[h].x=i;
		e[h].y=j;
		e[h].now=o;
	}
	memset(door,-1,sizeof(door));
	for(int i=1;i<=k;i++){
		int x1,x2,y1,y2,g;
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
		int tem1=x1-x2;
		int tem2=y1-y2;
		if(!tem1){
			if(tem2==1){
				door[x1][y1][2]=g;
				door[x2][y2][1]=g;
			}
			if(tem2==-1){
				door[x1][y1][1]=g;
				door[x2][y2][2]=g;
			}
		}
		if(!tem2){
			if(tem1==1){
				door[x1][y1][3]=g;
				door[x2][y2][4]=g;
			}
			if(tem1==-1){
				door[x1][y1][4]=g;
				door[x2][y2][3]=g;
			}
		}
	}
	scanf("%d",&s);
	for(int i=1;i<=s;i++){
		int x,y,q;
		scanf("%d%d%d",&x,&y,&q);
		b[x][y]|=(1<<(q-1));
	}
	S.push(c[1][1][0]);
	while(!S.empty()){
		int u=S.front();
		S.pop();
		for(int i=1;i<=4;i++){
			int x=e[u].x+mov[i][0];
			int y=e[u].y+mov[i][1];
			int now=e[u].now;
			if(b[x][y]>0)
			now=now|b[x][y];
			if(!a[x][y][now]){
				if(door[e[u].x][e[u].y][i]==-1){
					a[x][y][now]=a[e[u].x][e[u].y][e[u].now]+1;
					S.push(c[x][y][now]);
				}
				else
				if(door[e[u].x][e[u].y][i]>0){
					if(e[u].now&(1<<(door[e[u].x][e[u].y][i]-1))){
						a[x][y][now]=a[e[u].x][e[u].y][e[u].now]+1;
						S.push(c[x][y][now]);
					}
				}
			}
		}
	}
	int mi=0x3fffffff;
	for(int i=0;i<(1<<p);i++){
		if(a[n][m][i])
		mi=min(mi,a[n][m][i]);
	}
	if(mi!=0x3fffffff)
	cout<<mi;
	else 
	cout<<-1;
	return 0;
}