Maze

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN 51
using namespace std;
struct Node
{
    int x, y, step, key;
    friend bool operator < (Node a, Node b)
    {
        return a.step > b.step;
    }
};
int Map[MAXN][MAXN];
int pos[MAXN][MAXN][10];//存储该位置拥有的 钥匙种类
bool vis[MAXN][MAXN][1<<10];//最多10个门
int rec[MAXN][MAXN][MAXN][MAXN];// -2表示两点间有墙 大于或等于0表示两点间有门 -1表示什么都没有
int N, M, p, k;
void getMap()
{
    int x, y, x1, y1, x2, y2, op;
    memset(Map, 0, sizeof(Map));//0表示该位置什么都没有
    memset(rec, -1, sizeof(rec));//-1表示两个位置之间 什么都没有
    scanf("%d", &k);
    for(int i = 1; i <= k; i++)//k个地方有门 或者 有墙
    {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &op);
        if(op == 0)//墙
            rec[x1][y1][x2][y2] = rec[x2][y2][x1][y1] = -2;
        else//门
            rec[x1][y1][x2][y2] = rec[x2][y2][x1][y1] = op-1;
    }
    memset(pos, 0, sizeof(pos));
    int S;//钥匙数目
    scanf("%d", &S);
    while(S--)
    {
        scanf("%d%d%d", &x, &y, &op);
        Map[x][y] = 1;
        if(!pos[x][y][op-1])//该钥匙 还没有
            pos[x][y][op-1] = 1;
    }
}
bool judge(Node a)//是否越界
{
    return a.x >= 1 && a.x <= N && a.y >= 1 && a.y <= M;
}
int wall_or_door(Node a, Node b)//推断两个点间是否有 墙 或有门 或什么都没有
{
    return rec[a.x][a.y][b.x][b.y];
}
void BFS(int x, int y)
{
    priority_queue<Node> Q;
    int move[4][2] = {0,1, 0,-1, 1,0, -1,0};
    memset(vis, false, sizeof(vis));
    Node now, next;
    now.x = x, now.y = y, now.step = 0, now.key = 0;
    if(Map[now.x][now.y])//起点可能有钥匙 这里是个坑
    {
        for(int i = 0; i < 10; i++)
        {
            if(pos[now.x][now.y][i])
                now.key |= (1 << i);
        }
    }
    Q.push(now);
    vis[now.x][now.y][now.key] = true;
    while(!Q.empty())
    {
        now = Q.top();
        Q.pop();
        if(now.x == N && now.y == M)//到达终点
        {
            printf("%d\n", now.step);
            return ;
        }
        for(int k = 0; k < 4; k++)
        {
            next.x = now.x + move[k][0];
            next.y = now.y + move[k][1];
            next.step = now.step + 1;
            int t = wall_or_door(now, next);
            if(judge(next) && t != -2)//不能越界且中间不能有墙
            {
                //分有门 和 没有门 来讨论
                if(t >= 0)//有门
                {
                    next.key = now.key;
                    //先看是否有钥匙 要保证能到达目标位置
                    if(next.key & (1 << t))//有钥匙
                    {
                        //推断目标位置是否有钥匙
                        if(Map[next.x][next.y])//有钥匙 收集钥匙
                        {
                            for(int i = 0; i < 10; i++)
                            {
                                if(pos[next.x][next.y][i])
                                    next.key |= (1 << i);
                            }
                        }
                        if(!vis[next.x][next.y][next.key])//推断该状态 是否出现过
                        {
                            vis[next.x][next.y][next.key] = true;
                            Q.push(next);
                        }
                    }
                    //没有钥匙这条路眼下不能走
                }
                else//没有门
                {
                    next.key = now.key;
                    if(Map[next.x][next.y])//目标位置有钥匙
                    {
                        for(int i = 0; i < 10; i++)
                        {
                            if(pos[next.x][next.y][i])
                                next.key |= (1 << i);
                        }
                    }
                    if(!vis[next.x][next.y][next.key])
                    {
                        vis[next.x][next.y][next.key] = true;
                        Q.push(next);
                    }
                }
            }
        }
    }
    printf("-1\n");
}
int main()
{
    while(scanf("%d%d%d", &N, &M, &p) != EOF)
    {
        getMap();
        BFS(1, 1);
    }
    return 0;
}