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;
}