E题求调

#include<bits/stdc++.h>
#define LL long long
#define XX first
#define YY second
using namespace std;
const LL dx[4]={0,0,1,-1};
const LL dy[4]={1,-1,0,0};
struct node
{
	LL x,y,num;
};
LL n,m,t,dis[25][25],a[305][305],vis[305][305],sx,sy,ex,ey,cnt,f[25][3000005],mx;
char c[305][305];
queue<node>q;
pair<LL,LL> pt[25];
LL work(LL i,LL j)
{
	LL sx=pt[i].XX,sy=pt[i].YY,ex=pt[j].XX,ey=pt[j].YY;
	while(!q.empty())q.pop();
	q.push({sx,sy,0});
	memset(vis,0,sizeof(vis));
	while(!q.empty())
	{
		LL tx=q.front().x,ty=q.front().y,num=q.front().num;
		q.pop();
		for(int i=0;i<4;i++)
		{
			LL xx=tx+dx[i],yy=ty+dy[i];
			if(xx<1||n<xx||yy<1||m<yy||a[xx][yy]==1||vis[xx][yy]==1)continue;
			vis[xx][yy]=1;
			q.push({xx,yy,num+1});
			if(xx==ex&&yy==ey)return num+1;
		}
	}
	return 10000000;
}
int main()
{
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
			if(c[i][j]=='S')sx=i,sy=j;
			if(c[i][j]=='G')ex=i,ey=j;
			if(c[i][j]=='o')
			{
				pt[++cnt]={i,j};
			}
			if(c[i][j]=='#')a[i][j]=1; 
		}
	}
	pt[++cnt]={sx,sy},pt[++cnt]={ex,ey};
	for(int i=1;i<=cnt;i++)
	{
		for(int j=i+1;j<=cnt;j++)
		{
			dis[i][j]=dis[j][i]=work(i,j);
		}
	}	 
	memset(f,127,sizeof(f));
	f[cnt-1][1<<(cnt-2)]=0;
	for(int i=(1<<(cnt-2));i<=(1<<cnt)-1;i++)
	{
		if(((i>>(cnt-2))&1)==0)continue;
		for(int j=1;j<=cnt;j++)
		{
			if(((i>>(j-1))&1)==0)continue;
			for(int k=1;k<=cnt;k++)
			{
				f[k][i|(1<<(k-1))]=min(f[k][i|(1<<(k-1))],f[j][i]+dis[j][k]);
			}
		}
	}
	for(int i=(1<<(cnt-2));i<=(1<<cnt)-1;i++)
	{
		if(((i>>(cnt-1))&1)==0)continue;
		if(((i>>(cnt-2))&1)==0)continue;
		if(f[cnt][i]>t)continue;
		LL sum=0;
		for(int k=1;k<=cnt-2;k++)
		{
			if((i>>(k-1))&1)sum++;
		}
		mx=max(mx,sum);
	}
	if(mx==0)
	{
		puts("-1");
		return 0;
	}
	cout<<mx<<endl;
}