记录编号	133047	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-10-27 06:33:48	内存使用	6.99 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 0x3fffffff
using namespace std;
int n,m,p,k,xi,yi,xj,yj,gi,s,x,y,v;
int g[18][18][4][1029]={0},dis[18][18][1029];
bool flag[18][18][1029]={0};
vector<int> keys[18][18];
const int xx[4]={-1,0,1,0};
const int yy[4]={0,-1,0,1};
struct node{int x,y,w;};
bool pass(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m;}
void init(){
	memset(dis,0x3f,sizeof(dis));
	cin>>n>>m>>p>>k;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	        for(int w=0;w<=(1<<p);w++)
	            for(int pos=0;pos<4;pos++)
	            	g[i][j][pos][w]=1;
	for(int i=1;i<=k;i++){
		cin>>xi>>yi>>xj>>yj>>gi;
		if(gi==0){
			if(xi==xj){
				for(int w=0;w<=(1<<p);w++){
					if(yi<yj){g[xi][yi][3][w]=-1; g[xj][yj][1][w]=-1;}
					else{g[xi][yi][1][w]=-1; g[xj][yj][3][w]=-1;}
				}
			}
   			else{
				for(int w=0;w<=(1<<p);w++){
					if(xi<xj){g[xi][yi][2][w]=-1; g[xj][yj][0][w]=-1;}
					else{g[xi][yi][0][w]=-1; g[xj][yj][2][w]=-1;}
				}
			}
		}
		else{
			if(xi==xj){
				for(int w=0;w<=(1<<p);w++)
					if(((w>>(gi-1))&1)==0){
						if(yi<yj){g[xi][yi][3][w]=-1; g[xj][yj][1][w]=-1;}
						else{g[xi][yi][1][w]=-1; g[xj][yj][3][w]=-1;}
					}
			}
   			else{
				for(int w=0;w<=(1<<p);w++)
					if(((w>>(gi-1))&1)==0){
						if(xi<xj){g[xi][yi][2][w]=-1; g[xj][yj][0][w]=-1;}
						else{g[xi][yi][0][w]=-1; g[xj][yj][2][w]=-1;}
					}
			}
		}
	}
	cin>>s;
	for(int i=1;i<=s;i++){
		cin>>x>>y>>v;
		keys[x][y].push_back(v);
	}
}
queue<node> q;
void spfa(){
	dis[1][1][0]=0;
	q.push((node){1,1,0});
	flag[1][1][0]=true;
	while(!q.empty()){
		node now=q.front(); q.pop();
		for(int pos=0;pos<4;pos++){
			if(pass(now.x+xx[pos],now.y+yy[pos])){
				int wr=now.w;
				if(keys[now.x+xx[pos]][now.y+yy[pos]].size()!=0){
					for(int i=0;i<keys[now.x+xx[pos]][now.y+yy[pos]].size();i++){
						wr|=(1<<(keys[now.x+xx[pos]][now.y+yy[pos]][i]-1));
					}
				}
				if(g[now.x][now.y][pos][now.w]<0) continue;
				if(dis[now.x+xx[pos]][now.y+yy[pos]][wr]>dis[now.x][now.y][now.w]+1){
					dis[now.x+xx[pos]][now.y+yy[pos]][wr]=dis[now.x][now.y][now.w]+1;
					if(!flag[now.x+xx[pos]][now.y+yy[pos]][wr]){
						q.push((node){now.x+xx[pos],now.y+yy[pos],wr});
						flag[now.x+xx[pos]][now.y+yy[pos]][wr]=true;
					}
				}
			}
		}
	}
	int ans=INF;
	for(int w=0;w<=(1<<p);w++){
		if(dis[n][m][w]<ans) ans=dis[n][m][w];
	}
	if(ans<1e8) cout<<ans<<endl;
	else cout<<-1<<endl;
}
int main(){
	freopen("rescue.in","r",stdin);
	freopen("rescue.out","w",stdout);
	init();
	spfa();
	return 0;
}