链接

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int a[11][11][11][11];
int b[11][11][15];
int keys[11][11];
int xz[]={0,1,0,-1};
int yz[]={1,0,-1,0};
int n,m,p,k,l;
struct dian{
    int x,y,step;
    bool key[15];
};
queue<dian> q;
int main(){
    memset(a,-1,sizeof(a));
    scanf("%d%d%d",&n,&m,&p);
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        int x1,y1,x2,y2,q;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&q);
        a[x1][y1][x2][y2]=q;
        a[x2][y2][x1][y1]=q;
    }
    scanf("%d",&l);
    for(int i=1;i<=l;i++){
        int x,y,q;
        scanf("%d%d%d",&x,&y,&q);
        b[x][y][++keys[x][y]]=q;
    }
    dian old;
    old.x=1;
    old.y=1;
    old.step=0;
    memset(old.key,0,sizeof(old.key));
    dian newd,now;
    if(keys[old.x][old.y]!=0){//捡钥匙
        for(int i=1;i<=keys[old.x][old.y];i++){
            old.key[b[old.x][old.y][i]]=1;
        }
    }
    q.push(old);
    while(!q.empty()){
        now=q.front();
        q.pop();
        if(now.x==n&&now.y==m){//到达
            printf("%d",now.step);
            return 0;
        }
        for(int i=0;i<4;i++){
            newd.x=now.x+xz[i];
            newd.y=now.y+yz[i];//新点
            newd.step=now.step+1;
            for(int i=1;i<=14;i++){
                newd.key[i]=now.key[i];
            }
            if(newd.x<=n&&newd.x>=1&&newd.y<=m&&newd.y>=1){//判断越界
                if(a[now.x][now.y][newd.x][newd.y]==0)continue;//有墙
                if(keys[newd.x][newd.y]!=0){
                    for(int j=1;j<=keys[newd.x][newd.y];j++)
                        newd.key[b[newd.x][newd.y][j]]=1;//捡钥匙
                }
                if(a[now.x][now.y][newd.x][newd.y]!=-1)
                    if(newd.key[a[now.x][now.y][newd.x][newd.y]]==0)continue;//有门没钥匙
                q.push(newd);//入队
            }
        }
    }
    printf("-1");
    return 0;
}