拯救大兵瑞恩——状态压缩 + 复合BFS + 动态规划 + 坐标压缩

题目

代码

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 11;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int key[N*N], g[N*N][N*N], d[N*N][1<<N];
int n, m, p;
int get(int x, int y)
{
    return (x-1)*m+y;
}
int bfs()
{
    memset(d, -1, sizeof d);
    queue<PII> q;
    q.push({1, key[1]}); d[1][key[1]] = 0;
    
    while(q.size())
    {
        int loc = q.front().x, ky = q.front().y; q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int nx = (loc-1) / m + 1 + dx[i], ny = (loc-1) % m + 1 + dy[i];
            int nloc = get(nx, ny);
            if(nx < 1 || ny < 1 || nx > n || ny > m || !g[loc][nloc]) continue;
            if(~g[loc][nloc] && !(ky >> g[loc][nloc] & 1)) continue;
            int nky = ky | key[nloc];
            if(~d[nloc][nky]) continue;
            d[nloc][nky] = d[loc][ky] + 1;
            if(nloc == n*m) return d[nloc][nky];
            q.push({nloc, nky});
        }
    }
    
    return -1;
}
int main()
{
    cin >> n >> m >> p;
    int k;
    cin >> k;
    memset(g, -1, sizeof g);
    for(int i = 1; i <= k; i++)
    {
        int a1, b1, a2, b2, c;
        cin >> a1 >> b1 >> a2 >> b2 >> c;
        int a = get(a1, b1);
        int b = get(a2, b2);
        g[a][b] = c;
        g[b][a] = c;
    }
    
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int t = get(a, b);
        key[t] |= 1 << c;
    }
    
    cout << bfs();
}