题目描述

难度分:$1673$

输入$n$，$m(1 \leq n,m \leq 300)$，$t(1 \leq t \leq 2 \times 10^6)$和一个$n$行$m$列的网格图。

• S为起点（恰好一个）。

• G为终点（恰好一个）。

• .为空地。

• #为墙壁。

• o为糖果（至多$18$个）。

你需要从起点走到终点。每一步可以上下左右四个方向走到相邻的非墙壁格子上，不能出界，可以重复访问同一个格子。

注：如果走到终点，可以继续走，只要最后在终点就行，至多走$t$步。

输出你至多能收集多少个糖果（走到o即可收集，同一个格子只能收集一次）。

如果无法在$t$步内到达终点，输出$-1$。

输入样例$1$

3 3 5
S.G
o#o
.#.

输出样例$1$

1

输入样例$2$

3 3 1
S.G
.#o
o#.

输出样例$2$

-1

输入样例$3$

5 10 2000000
S.o..ooo..
..o..o.o..
..o..ooo..
..o..o.o..
..o..ooo.G

输出样例$3$

18

算法

BFS+状压DP

这个题乍一看感觉是暴力深搜或者宽搜，但仔细想想这么做肯定会超时。主要的突破点在于糖果的数量最多为$18$个，这个数量是可以状压的，算上起点和终点，$2^{20}$大概是$10^6$的量级，很有可能是一个状压DP。

状态定义

为了方便处理，把起点和终点都看做糖果，$f[mask][i]$表示当前在$i$位置，且收集糖果的状态为$mask$的情况下，最少的步数。

状态转移

对于状态$f[mask][j]$，枚举它的下一个位置$i$就可以进行状态转移，转移方程为

$f[mask \lor 2^i][i]=min_j(f[mask][j] + dist[j][i]$)

其中$j$可以到达$i$，$dist[j][i]$表示$j$到$i$的最短路，可以枚举糖果对，通过BFS计算糖果两两之间的最短距离给预处理出来。

最后枚举$mask$，状态要包含起点和终点，维护$f[mask][dest]$中$1$的最大值$mx$即可（其中$dest$为终点），答案还需要去掉起点和终点，因此为$mx-2$。

复杂度分析

设糖果的数量为$m$，地图的高和宽是$n$的规模。

时间复杂度

利用$BFS$求起点、终点、以及每个糖果之间最短距离时间复杂度为$O(m^2n^2)$。之后的状压DP，状态数量为$2^m$规模，算上内层两层循环枚举两个相邻的位置，时间复杂度为$O(m^22^m)$。因此，算法整体的时间复杂度为$O(n^2m^2+m^22^m)$。

空间复杂度

$dp$数组是$O(m2^m)$规模，$dist$数组是$O(m^2)$规模，其他的辅助数组都是$O(n^2)$规模。考虑到$n$比$m$大很多，因此额外空间的痛点在于$O(n^2)$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> PII;

const int N = 301, M = 21, INF = 0x3f3f3f3f;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int h, w, t, n, so, to;
char g[N][N];
int dist[M][M], f[1<<M][M];
bool st[N][N];

int bfs(int x1, int y1, int x2, int y2) {
    memset(st, 0, sizeof st);
    int step = 0;
    queue<PII> q;
    q.push({x1, y1});
    while(!q.empty()) {
        int sz = q.size();
        while(sz--) {
            auto cur = q.front();
            q.pop();
            int x = cur.first, y = cur.second;
            if(x == x2 && y == y2) return step;
            if(st[x][y]) continue;
            st[x][y] = true;
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if(1 <= nx && nx <= h && 1 <= ny && ny <= w && g[nx][ny] != '#') {
                    q.push({nx, ny});
                }
            }
        }
        step++;
    }
    return INF;
}

int main() {
    scanf("%d%d%d", &h, &w, &t);
    vector<PII> p;
    for(int i = 1; i <= h; i++) {
        scanf("%s", g[i] + 1);
        for(int j = 1; j <= w; j++) {
            if(g[i][j] == 'S') {
                so = p.size();
                g[i][j] = 'o';
                p.push_back({i, j});
            }else if(g[i][j] == 'G') {
                to = p.size();
                g[i][j] = 'o';
                p.push_back({i, j});
            }else if(g[i][j] == 'o') {
                p.push_back({i, j});
            }
        }
    }
    n = p.size();
    swap(p[to], p[n - 1]); to = n - 1;
    swap(p[so], p[n - 2]); so = n - 2;
    memset(dist, 0x3f, sizeof dist);
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            if(i == j) {
                dist[i][j] = 0;
            }else {
                dist[i][j] = dist[j][i] = bfs(p[i].first, p[i].second, p[j].first, p[j].second);
            }
        }
    }
    if(dist[so][to] > t) {
        puts("-1");      // 起点终点不连通
        return 0;
    }
    if(n <= 2) {
        puts("0");       // 图上出起点终点之外没有糖果
        return 0;
    }
    // 状压DP
    memset(f, 0x3f, sizeof(f));
    f[1<<(n - 2)][n - 2] = 0;        // 刚开始在起点
    for(int mask = 0; mask < 1<<n; mask++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                f[mask|(1<<i)][i] = min(f[mask|(1<<i)][i], f[mask][j] + dist[j][i]);
            }
        }
    }
    int ans = 0;
    for(int mask = 0; mask < 1<<n; mask++) {
        if((mask>>(n - 1)&1) == 0 || (mask>>(n - 2)&1) == 0) continue;     // 必须包含起点和终点
        if(f[mask][n - 1] <= t) {
            ans = max(ans, __builtin_popcount(mask));
        }
    }
    printf("%d", ans - 2);
    return 0;
}