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

广搜+状压dp，不知道哪里挂了，样例全过

#include <bits/stdc++.h>
using namespace std;
#define int long long

int h, w, t, dis[30][30], dep[310][310], os, f[30][1048600], ans = -1;
char mp[310][310];
bool b[310][310];
struct XY
{
    int x, y;
} d[30], st, g;

void bfs(int s)
{
    queue<XY> q;
    memset(b, 0, sizeof(b)), memset(dep, 0, sizeof(dep));
    q.push(d[s]), b[d[s].x][d[s].y] = 1;
    while(q.size())
    {
        XY now = q.front();
        if(now.x+1 <= h && mp[now.x+1][now.y] != '#' && !b[now.x+1][now.y])
            dep[now.x+1][now.y] = dep[now.x][now.y]+1, q.push({now.x+1, now.y}), b[now.x+1][now.y] = 1;
        if(now.x-1 > 0 && mp[now.x-1][now.y] != '#' && !b[now.x-1][now.y])
            dep[now.x-1][now.y] = dep[now.x][now.y]+1, q.push({now.x-1, now.y}), b[now.x-1][now.y] = 1;
        if(now.y+1 <= w && mp[now.x][now.y+1] != '#' && !b[now.x][now.y+1])
            dep[now.x][now.y+1] = dep[now.x][now.y]+1, q.push({now.x, now.y+1}), b[now.x][now.y+1] = 1;
        if(now.y-1 > 0 && mp[now.x][now.y-1] != '#' && !b[now.x][now.y-1])
            dep[now.x][now.y-1] = dep[now.x][now.y]+1, q.push({now.x, now.y-1}), b[now.x][now.y-1] = 1;
        q.pop();
    }
    for(int i = 0; i <= os; i++) dis[s][i] = dep[d[i].x][d[i].y];
}

signed main()
{
    scanf("%lld%lld%lld", &h, &w, &t), memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
        {
            cin >> mp[i][j];
            if(mp[i][j] == 'S') d[0] = {i, j};
            if(mp[i][j] == 'o') d[++os] = {i, j};
        }
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
            if(mp[i][j] == 'G') d[++os] = {i, j};
    for(int i = 0; i <= os; i++) bfs(i);
    if(dis[0][os] > t) {printf("-1"); return 0;}
    f[0][1] = 0;
    for(int i = 0; i < (1<<(os+1)); i++)
        for(int j = 0; j <= os; j++)
        {
            if(f[j][i] > t) continue;
            for(int k = 0; k <= os; k++)
                f[k][i|(1<<k)] = min(f[k][i|(1<<k)], f[j][i]+dis[j][k]);
        }
    for(int i = 0; i < (1<<(os+1)); i++)
    { 
        if(f[os][i] > t) continue;
        int s = 0;
        for(int j = 1; j <= i; j <<= 1)
            if(i&j) s++;
        ans = max(ans, s);
    }
    printf("%lld", ans-2);

    return 0;
}