这道题一眼望上去看起来是最短路或者广搜,但是 $k\le 2\times 10^6$,让你没法下手。

不过发现有糖果的格子最多只有 $18$ 个,加上起点终点只有 $20$ 个点有用,那么什么样的题目数据范围是 $20$ 呢?

不难算出 $2^{20}$ 大概是一百万,于是就想到了状压DP。

定义 $f[i][j]$ 表示当前点为 $i$,状态为 $j$ 时的最短距离。定义 $d[i][j]$ 表示点 $i$ 到 $j$ 的距离,如果不连通则 $d[i][j]=\infty$。

先用广搜算出所有有用的点(不妨设是 $t$ 个)两两之间的距离,然后枚举下一个走的点 $k$,可以得到:
$f[i][j]=\min(f[i][j],f[k][j-2^k]+d[i][k])$

那么对于距离不超过要求的状态,求最大数量的 $1$ 即可,可以使用 lowbit 每次砍掉一位计算。

时间复杂度 $O(t^2\times 2^t)$。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e2 + 5, MR = 1e4 + 5, MN = 21, MM = 1 << 19;
int n, m, l, ans, sx, sy, ex, ey, num, mp[MAXN][MAXN], used[MAXN][MAXN], g[MN][MN], f[MN][MM];
char ch[MAXN][MAXN];
struct node{
    int x, y;
}d[MAXN];
struct step{
    int x, y, st;
};
int lowbit(int x){return x & -x;}
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void bfs(int p, int q){
    queue<step>pq;
    pq.push({p, q, 0});
    memset(used, 0, sizeof(used));
    used[p][q] = 1;
    while(!pq.empty()){
        int hx = pq.front().x, hy = pq.front().y, hst = pq.front().st;
        pq.pop();
        for(int i = 0;i < 4;i ++){
            int tx = hx + dx[i], ty = hy + dy[i];
            if(used[tx][ty] || tx <= 0 || ty <= 0 || tx > n || ty > m || ch[tx][ty] == '#')continue;
            used[tx][ty] = 1;
            if(mp[tx][ty])g[mp[p][q]][mp[tx][ty]] = g[mp[tx][ty]][mp[p][q]] = hst + 1;
            pq.push({tx, ty, hst + 1});
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &l);
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin >> ch[i][j];
            if(ch[i][j] == 'S')sx = i, sy = j, mp[i][j] = ++ num, d[num] = {i, j};
            if(ch[i][j] == 'G')ex = i, ey = j, mp[i][j] = ++ num, d[num] = {i, j};
            if(ch[i][j] == 'o')mp[i][j] = ++ num, d[num] = {i, j};
        }
    }
    int ppp = mp[sx][sy];
    swap(mp[sx][sy], mp[d[num - 1].x][d[num - 1].y]);
    swap(d[num - 1], d[ppp]);
    ppp = mp[ex][ey];
    swap(mp[ex][ey], mp[d[num].x][d[num].y]);
    swap(d[num], d[ppp]);
    for(int i = 1;i <= num;i ++){
        bfs(d[i].x, d[i].y);
        for(int j = 1;j <= num;j ++){
            if(!used[d[j].x][d[j].y])g[i][j] = g[j][i] = 1e9;
        }
    }
    if(g[num - 1][num] > l){
        puts("-1");
        return 0;
    }
    memset(f, 0x3f, sizeof(f));
    for(int i = 1;i <= num - 2;i ++)f[i][1 << i] = g[i][num - 1];
    for(int k = 0;k < (1 << num - 1) - 1;k ++){
        for(int i = 1;i <= num - 2;i ++){
            if((1 << i) & k){
                for(int j = 1;j <= num - 2;j ++){
                    if(i == j || (1 << j) & k)continue;
                    f[j][k | (1 << j)] = min(f[j][k | (1 << j)], f[i][k] + g[i][j]);
                }
            }
        }
    }
    for(int i = 1;i <= num - 2;i ++){
        for(int k = 0;k < (1 << num - 1) - 1;k ++){
            if(k & (1 << i)){
                if(f[i][k] + g[i][num] <= l){
                    int res = 0, pp = k;
                    while(pp){
                        res ++;
                        pp -= lowbit(pp);
                    }
//                  printf("%d %d %d\n", k, res, f[i][k] + g[i][num]);
                    ans = max(ans, res);
                }
            }
        }
    }
    printf("%d", ans);
    return 0;
}

作者 xieliren

乐观乐观再乐观

发表回复