Title address:

https://www.acwing.com/problem/content/description/1133/

In 1944, special forces Mike received an order from the Ministry of defense to rush to an isolated island in the Pacific Ocean to rescue Private Ryan captured by the enemy. Ryan was imprisoned in a maze with complex terrain, but fortunately Mike got the topographic map of the maze. The shape of the maze is a rectangle, and its north-south direction is divided into N N N line, the east-west direction is divided into M M M column, so the whole maze is divided into N × M N×M N × M units. The position of each cell can be represented by an ordinal number pair (cell row number, cell column number). Adjacent in the North-South or east-west direction 2 2 The two units may be interconnected, or there may be a locked door or an insurmountable wall. Note: the door can pass through from two directions, that is, it can be regarded as an undirected edge. Some units in the maze store keys. The same unit may store multiple keys, and all doors are divided into two P P Class P: the keys to open the same class of doors are the same, and the keys to different classes of doors are different. Private Ryan was held in the southeast corner of the maze, i.e ( N , M ) (N,M) In unit (N,M) and in a coma. The maze has only one entrance, in the northwest corner. In other words, Mike can enter directly ( 1 , 1 ) (1,1) (1,1) unit. In addition, the time for the microphone to move from one unit to another adjacent unit is 1 1 1. The time of taking the key of the unit and opening the door with the key can be ignored. Try to design an algorithm to help Mike reach Ryan's unit in the fastest way and rescue Private Ryan.

Input format:
The first line has three integers, representing N , M , P N,M,P N. M, the value of P. The second line is an integer k k k. Represents the total number of doors and walls in the maze. next k k k rows, each containing five integers, X i 1 , Y i 1 , X i 2 , Y i 2 , G i X_{i1},Y_{i1},X_{i2},Y_{i2},G_i Xi1, Yi1, Xi2, Yi2, Gi: when G i ≥ 1 G_i≥1 When Gi ≥ 1, it means ( X i 1 , Y i 1 ) (X_{i1},Y_{i1}) (Xi1, Yi1) unit and ( X i 2 , Y i 2 ) (X_{i2},Y_{i2}) There is a second fan between (Xi2, Yi2) units G i G_i Gate of Gi ， class, when G i = 0 G_i=0 Gi = 0 indicates ( X i 1 , Y i 1 ) (X_{i1},Y_{i1}) (Xi1, Yi1) unit and ( X i 2 , Y i 2 ) (X_{i2},Y_{i2}) (Xi2, Yi2) there is an insurmountable wall between the units. The next line contains an integer S S S. Indicates the total number of keys stored in the maze. next S S S line, each line contains three integers X i 1 , Y i 1 , Q i X{i1},Y_{i1},Q_i Xi1,Yi1, Qi, indicating ( X i 1 , Y i 1 ) (X{i1},Y_{i1}) (Xi1,Yi1) there is one in the unit that can open the second Q i Q_i The key of Qi # type door.

Output format:
Output the shortest time for Mike to rescue Private Ryan. If the problem has no solution, output − 1 -1 −1.

Data range:
∣ X i 1 − X i 2 ∣ + ∣ Y i 1 − Y i 2 ∣ = 1 |X_{i1}−X_{i2}|+|Y_{i1}−Y_{i2}|=1 ∣Xi1​−Xi2​∣+∣Yi1​−Yi2​∣=1
0 ≤ G i ≤ P 0≤G_i≤P 0≤Gi​≤P
1 ≤ Q i ≤ P 1≤Q_i≤P 1≤Qi​≤P
1 ≤ N , M , P ≤ 10 1≤N,M,P≤10 1≤N,M,P≤10
1 ≤ k ≤ 150 1≤k≤150 1≤k≤150

In essence, it is the problem of finding the shortest path by implicit graph. You can add one dimension to the position, that is, what is the "state" of the key in your current hand. This state can be expressed by binary state compression, that is, state s determines whether the key numbered id is already in your hand by calculating whether s > > id - 1 & 1 is 1. The initial position is ( 1 , 1 ) (1,1) (1,1), key status is 0 0 0, from the starting point of the implicit graph, once the location is found ( n , m ) (n,m) The shortest path of the point of (n,m) is the answer. In terms of state transition, if there is no key in the current position, take one step in four directions (that is, the edge right to the next position is 1 1 1)； If there are keys in the current position and the current state does not hold all the keys in the current position, then pick up the keys (because it does not take time to pick up the keys, so picking up the keys will surely lead to the optimal solution). At this time, the edge weight is 0 0 0 This is 0 − 1 0-1 0 − 1 shortest path problem can be solved by using double ended queue BFS.

Of course, the writing method of this problem is not unique. You can also directly pick up the key in the initial state as the starting point of the implicit graph, and then pick up the key immediately every time you go to a grid (combine "go" and pick up the key into 1 1 Step 1), so that the edge weight of the entire implicit graph is 1 1 1. Queue BFS can be used directly. That's OK.

The code is as follows:

#include <iostream>
#include <cstring>
#include <deque>
#include <set>
using namespace std;

typedef pair<int, int> PII;

// E stores the number of edges of the matrix (here, the number of edges is the imaginary edges between the lattices)
const int N = 11, M = N * N, E = 400, P = 1 << 10;
// n is the number of rows, m is the number of columns, p is the number of types of doors (keys), and k is the total number of doors and walls
int n, m, p, k;
int h[M], e[E], w[E], ne[E], idx;
// g[i][j] is the one-dimensional coordinate corresponding to the position (i, j), and key[i] is the key state of one-dimensional coordinate I (there may be multiple keys)
int g[N][N], key[M];
int dist[M][P];
bool st[M][P];
set<PII> edges;

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

// Mapping
void build() {
    int d[] = {1, 0, -1, 0, 1};
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        	// Enumerate four directions
            for (int u = 0; u < 4; u++) {
                int nx = i + d[u], ny = j + d[u + 1];
                if (1 <= nx && nx <= n && 1 <= ny && ny <= m) {
                    int a = g[i][j], b = g[nx][ny];
                    if (!edges.count({a, b})) add(a, b, 0);
                }
            }
}

// Double ended queue BFS, simulated heap optimization, Dijkstra write
int bfs() {
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;

    deque<PII> dq;
    dq.push_back({1, 0});

    while (dq.size()) {
        auto t = dq.front();
        dq.pop_front();

        if (st[t.first][t.second]) continue;

        if (t.first == n * m) return dist[t.first][t.second];

        st[t.first][t.second] = true;

		// If there is a key in the current position and it is not finished, take the key first
        if (key[t.first] && (t.second & key[t.first]) != key[t.first]) {
            int state = t.second | key[t.first];
            if (dist[t.first][state] > dist[t.first][t.second]) {
                dist[t.first][state] = dist[t.first][t.second];
                dq.push_front({t.first, state});
            }
        } else
        	// Otherwise, it means that the key in the current position is full (or there is no key in the current position), and go one grid in four directions
            for (int i = h[t.first]; ~i; i = ne[i]) {
                int j = e[i];
                if (st[j][t.second]) continue;
                // If the current side needs a key, but there is no corresponding key in hand, you can't go. Skip this side
                if (w[i] && !(t.second >> w[i] - 1 & 1)) continue;
                
                if (dist[j][t.second] > dist[t.first][t.second] + 1) {
                    dist[j][t.second] = dist[t.first][t.second] + 1;
                    dq.push_back({j, t.second});
                }
            }
    }

    return -1;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &p, &k);

	// Two dimensional to one dimensional
    for (int i = 1, t = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            g[i][j] = t++;

    memset(h, -1, sizeof h);

    while (k--) {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        int a = g[x1][y1], b = g[x2][y2];
        edges.insert({a, b}), edges.insert({b, a});
        // 0 means there is no wall and you can go
        if (c) add(a, b, c), add(b, a, c);
    }

    build();

    int s;
    scanf("%d", &s);
    while (s--) {
        int x, y, id;
        scanf("%d%d%d", &x, &y, &id);
        key[g[x][y]] |= 1 << id - 1;
    }

    printf("%d\n", bfs());

    return 0;
}

Spatiotemporal complexity O ( n m 2 p ) O(nm2^p) O(nm2p).