洛谷 P4011 孤岛营救问题（BFS分层图最短路，状态压缩）

题目链接

https://www.luogu.com.cn/problem/P4011

思路

注意到$n$和$m$最大为$10$，$s$最大为$14$。

我们考虑对已获得的钥匙进行二进制状态压缩。

我们可以用$dist[i][j][k]$表示走到$(i,j)$这个格子，且当前已有钥匙的状态为$k$时的最短距离。

显然，我们直接使用BFS求最短路即可。

注意：同一个格子可能有多把钥匙，一开始的$(1,1)$也可能有钥匙。

代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

typedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;

const int N = 10 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

std::mt19937 rnd(time(0));

int n, m, p, k, s, ans;
int G[N * N][N * N];
vector<int> Q[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool st[N][N][2 << 14];
map<int, int>ha;
struct node
{
    int x, y, stu, sum;
};
void bfs()
{
    queue<node>q;
    st[1][1][0] = true;
    q.push({1, 1, 0, 0});
    if (Q[1][1].size())
    {
        int op = 0;
        for (int val : Q[1][1]) op |= (1 << (ha[val] - 1));
        st[1][1][op] = true;
        q.push({1, 1, op, 0});
    }
    while (q.size())
    {
        int cx = q.front().x;
        int cy = q.front().y;
        int stu = q.front().stu;
        int sum = q.front().sum;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int tx = cx + dx[i];
            int ty = cy + dy[i];
            if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
            if (G[(cx - 1) * m + cy][(tx - 1) * m + ty] == 0) continue;//墙,过不去
            int key = G[(cx - 1) * m + cy][(tx - 1) * m + ty];
            if (key != -1 && !ha.count(key)) continue;//不可能有对应的钥匙,过不去
            bool ok = false;
            if (key == -1)
            {
                //随便过
                ok = true;
            }
            else
            {
                int op = 1 << (ha[key] - 1);
                if ((stu | op) == stu) ok = true;
            }
            if (!ok) continue;//过不去
            if (tx == n && ty == m)
            {
                ans = min(ans, sum + 1);
                return;
            }
            int stu1 = stu;
            if (Q[tx][ty].size())
            {
                int op = 0;
                for (int val : Q[tx][ty]) op |= (1 << (ha[val] - 1));
                int stu2 = stu | op;
                if (stu1 != stu2)
                {
                    if (!st[tx][ty][stu2])
                    {
                        st[tx][ty][stu2] = true;
                        q.push({tx, ty, stu2, sum + 1});
                    }
                }
            }
            if (st[tx][ty][stu1]) continue;
            st[tx][ty][stu1] = true;
            q.push({tx, ty, stu1, sum + 1});
        }
    }
}
void solve(int test_case)
{
    ans = inf;
    cin >> n >> m >> p;
    cin >> k;
    for (int i = 1; i <= n * m; i++)
    {
        for (int j = 1; j <= n * m; j++)
        {
            G[i][j] = -1;
        }
    }
    for (int i = 1, cx, cy, tx, ty, g; i <= k; i++)
    {
        cin >> cx >> cy >> tx >> ty >> g;
        G[(cx - 1) * m + cy][(tx - 1) * m + ty] = g;
        G[(tx - 1) * m + ty][(cx - 1) * m + cy] = g;
    }
    cin >> s;
    int cnt = 0;
    for (int i = 1, x, y, q; i <= s; i++)
    {
        cin >> x >> y >> q;
        Q[x][y].push_back(q);
        if (!ha.count(q))
        {
            ha[q] = ++cnt;
        }
    }
    bfs();
    if (ans == inf) ans = -1;
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve(i);
    }
    return 0;
}

原文地址：https://blog.csdn.net/weixin_74754298/article/details/143780930

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！