1、将矩阵中的每一个点映射成为图中的每一个点。
2、然后分析每一个映射点之间的关系。是可行走的通路还是墙，还是门， 然后把点和点之间的关系存储下来。
3、通过存储的关系建图。
4、读入哪些点有钥匙，然后把这些矩阵点映射成为图中的点，然后通过二进制来存储。
5、通过双端bfs来解决问题。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
int n, m, p, k;
const int N = 20, K = 200;

int h[N * N], e[2 * K], w[2 * K], ne[2 * K], idx;
int dist[N * N][1 << 10];
int key[N * N];
bool st[N * N][1 << 10];
int g[N][N];
set<PII> wg;
int t = 1;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void build()
{
    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            for (int t = 0; t < 4; t ++)
            {
                int a = i + dx[t], b = j + dy[t];
                if (a <= 0 || a > n || b <= 0 || b > m) continue;
                a = g[a][b], b = g[i][j];
                if (! wg.count({a, b})) add(a, b, 0);
            }
}

int bfs()
{
    memset(dist, 0x3f, sizeof dist);
    deque<PII> q;
    q.push_back({1, 0});
    dist[1][0] = 0;

    while (q.size())
    {
        PII t = q.front();
        q.pop_front();

        if (t.x == n*m) return dist[t.x][t.y];

        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;

        if (key[t.x])
        {
            int state = t.y | key[t.x];
            if (dist[t.x][state] > dist[t.x][t.y])
            {
                dist[t.x][state] = dist[t.x][t.y];
                q.push_front({t.x, state});
            }
        }

        for (int i = h[t.x]; ~i; i = ne[i])
        {
            int j = e[i];
            if (w[i] && !(t.y >> (w[i] - 1) & 1)) continue;
            if (dist[j][t.y] > dist[t.x][t.y] + 1)
            {
                dist[j][t.y] = dist[t.x][t.y] + 1;
                q.push_back({j, t.y});
            }
        }
    }


    return -1;
}

int main(void)
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> p; 
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            g[i][j] = t ++;
    cin >> k;
    while (k --)
    {
        int a, b, c, d, w;
        cin >> a >> b >> c >> d >> w;
        a = g[a][b], b = g[c][d];
        wg.insert({a, b}), wg.insert({b, a});
        if (w) add(a, b, w), add(b, a, w);
    }
    build();
    cin >> k;
    while (k --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int t = g[a][b];
        key[t] |= 1 << c - 1;
    }
    cout << bfs() << endl;
    return 0;
}