二分电池容量。
至于检查答案是否合法,我们注意到有用的点只有 F,G,Y,其他的点都是无用的。这三种点加起来最多 16 个(the sum of energy pools and power switches is less than 15)。我们就可以在图中找这三种点,对他们状压。
具体地,令 \(f(i,s)\) 表示当前点为 \(i\),其他点的经过状态为 \(s\)(状态压缩)的最大剩余能量,则有 \(f(j,s\cup\{j\})=\max{f(i,s)-\operatorname{dis}(i,j)}\),\(\operatorname{dis}(i,j)\) 表示点 \(i\) 到点 \(j\) 的距离,用 bfs 预处理。我们初始化将所有 \(f(i,s)\) 赋为 \(-1\),\(f(x,\{x\})=mid\)(\(x\) 为起点)。在 dp 过程中如果发现当前枚举的 \(s\) 包含了所有的 Y 点且 \(f(i,s)\) 不为 \(-1\),说明能够有一种方案使得所有 Y 点都被经过,直接 return true
。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=15,nxt[4][2]={0,1,1,0,0,-1,-1,0};
int dp[N+10][(1<<N)+10];
int n,m,dis[N*N+10][N*N+10];
char s[N+10][N+10];
bool vis[N+10][N+10];
struct node
{
int x,y,s;
node(int x,int y,int s) : x(x),y(y),s(s) {}
node() {}
}p[N+10],que[N+10];
int h=1,t=0;
int bfs(int x,int y) // point x to point y
{
memset(que,0,sizeof(que));
h=1;t=0;
memset(vis,0,sizeof(vis));
que[++t]=node(p[x].x,p[x].y,0);
vis[p[x].x][p[x].y]=1;
while(h<=t)
{
node head=que[h++];
if(head.x==p[y].x && head.y==p[y].y) return /*(puts("LHTDULIU"),*/head.s;
for(int i=0;i<4;i++)
{
int tx=head.x+nxt[i][0],ty=head.y+nxt[i][1];
if(vis[tx][ty] || s[tx][ty]=='D' ||
tx<1 || tx>n || ty<1 || ty>m) continue;
que[++t]=node(tx,ty,head.s+1);
vis[tx][ty]=1;
}
}
return -1;
}
int st,cnt=0,ac=0;
bool check(int en) // en:middle(energy)
{
memset(dp,-1,sizeof(dp));
dp[st][1<<(st-1)]=en;
int all_state=1<<cnt;
for(int sta=0;sta<all_state;sta++)
{
for(int i=1;i<=cnt;i++) //i:from
{
if(!(sta&(1<<(i-1)))) continue;
if(dp[i][sta]==-1) continue;
if((sta&ac)==ac) return true;
for(int j=1;j<=cnt;j++)
{
if(sta&(1<<(j-1))) continue;
if(dis[i][j]==-1) continue;
if(dp[i][sta]<dis[i][j]) continue;
int zzt=sta|(1<<(j-1));
dp[j][zzt]=max(dp[j][zzt],dp[i][sta]-dis[i][j]);
if(s[p[j].x][p[j].y]=='G') dp[j][zzt]=en;
}
}
}
return false;
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
if(n==0 && m==0) break;
cnt=0;
ac=0;
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='G')
{
p[++cnt]=node(i,j,0);
}
else if(s[i][j]=='F')
{
st=++cnt;
p[cnt]=node(i,j,0);
}
else if(s[i][j]=='Y')
{
cnt++;
ac|=(1<<(cnt-1));
p[cnt]=node(i,j,0);
}
}
}
memset(dp,-1,sizeof(dp));
memset(dis,-1,sizeof(dis));
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
dis[i][j]=dis[j][i]=bfs(i,j);
int l=1,r=10000,ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d",ans);
putchar('\n');
}
return 0;
}
/*
5 5
GDDSS
SSSFS
SYGYS
SGSYS
SSYSS
5 5
GDDSS
SSSFS
SYGYS
SGSYS
SSYSS
5 5
GDDSS
SSSFS
SYGYS
SGSYS
SSYSS
0 0
*/