记录编号	236823	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	粘粘自喜	是否通过	通过
代码语言	C++	运行时间	0.096 s
提交时间	2016-03-15 18:04:23	内存使用	0.57 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define inf 210000000
int n,m,p,K,S,map[16][16][16][16],ans,own[11]={0},use[16][16]={0};
int xi[4]={-1,0,0,1},yi[4]={0,-1,1,0};
bool key[16][16][11]={0};
void dfs(int x,int y,int z,int lx,int ly)
{
    int i,j,xx,yy;
    bool ff=false;
    if(x==n&&y==m){
        ans=min(ans,z);
        return ;
    }
    if((use[x][y]>5)||(z+n+m-x-y>=ans)) return ;
    for(i=1;i<=p;++i)
      if(key[x][y][i]){
        own[i]+=1;
        ff=true;
      }
    for(i=0;i<=3;++i){
        xx=x+xi[i];yy=y+yi[i];
        if(xx==lx&&yy==ly&&!ff) continue;
        if(xx>0&&xx<=n&&yy>0&&yy<=m){
            if(map[x][y][xx][yy]<0||own[map[x][y][xx][yy]]){
                use[xx][yy]+=1;
                dfs(xx,yy,z+1,x,y);
                use[xx][yy]-=1;
            }
        }
    }
    for(i=1;i<=p;++i)
      if(key[x][y][i])
        own[i]-=1;
}
int main()
{
    freopen("rescue.in","r",stdin);
    freopen("rescue.out","w",stdout);
    int i,j,x1,y1,x2,y2,x,y,z;
    scanf("%d%d%d%d",&n,&m,&p,&K);
    memset(map,128,sizeof(map));
    for(i=1;i<=K;++i){
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&z);
        map[x1][y1][x2][y2]=map[x2][y2][x1][y1]=z;
    }
    scanf("%d",&S);
    for(i=1;i<=S;++i){
        scanf("%d%d%d",&x,&y,&z);
        key[x][y][z]=true;
    }
    ans=inf;
    dfs(1,1,0,0,0);
    ans=(ans==inf?-1:ans);
    printf("%d\n",ans);
}