其實思路很簡單，只是敲代碼的時候很容易敲錯，MD，居然為了一個Pn>=n寫成了Pn>n NC地檢查了一個上午。如果是現(xiàn)場就悲劇了。。。
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 1000000000
int const maxn=15;
struct position
{
int x,y;
}pos[maxn];
int dp[1<<maxn][maxn];//初始時候為-1
int sx,sy;
int mat[maxn][maxn];//存地圖
int index[maxn][maxn];//存標號，初始為-1
int n,m;
int Pn,Gn;//開關(guān)數(shù)，能量數(shù)
void input()//n,m已存
{
memset(mat,0,sizeof(mat));
for(int i=0;i<n;i++){
char s[100];
scanf("%s",s);
for(int j=0;j<m;j++){
if(s[j]=='S')mat[i][j]=0;
else if(s[j]=='F'){sx=i;sy=j;mat[i][j]=0;}
else if(s[j]=='G'){mat[i][j]=1;}
else if(s[j]=='Y'){mat[i][j]=2;}
else if(s[j]=='D'){mat[i][j]=-1;}
}
}
}
int ind;
void getIndex()
{
ind=0;
memset(index,-1,sizeof(index));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(mat[i][j]==2)
{
pos[ind].x=i;
pos[ind].y=j;
index[i][j]=ind++;
}
}
Pn=ind;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(mat[i][j]==1)
{
pos[ind].x=i;
pos[ind].y=j;
index[i][j]=ind++;
}
}
Gn=ind-Pn;
}
struct node
{
int x,y;
int step;
node (int xx,int yy,int ss){x=xx;y=yy;step=ss;}
node (){}
};
bool god(int x,int y){
if(x>=0&&x<n&&y>=0&&y<m&&mat[x][y]!=-1)return true;
else return false;
}
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int v[maxn][maxn];
int dis[maxn][maxn];
void predo(int i)//預(yù)處理出最短路
{
memset(v,0,sizeof(v));
for(int j=0;j<ind;j++)
dis[i][j]=INF;
queue<node>Q;
node t(pos[i].x,pos[i].y,0);
v[t.x][t.y]=1;
Q.push(t);
//
while(!Q.empty())
{
t=Q.front();Q.pop();
if(index[t.x][t.y]!=-1)
dis[i][index[t.x][t.y]]=t.step;
for(int i=0;i<4;i++)
{
int nx=t.x+dir[i][0];
int ny=t.y+dir[i][1];
if( god(nx,ny)&& (!v[nx][ny]) )
{
node nt(nx,ny,t.step+1);
Q.push(nt);
v[nx][ny]=1;
}
}
}
}
bool DP(int mid)
{
int nn=(1<<ind);
for(int j=0;j<nn;j++){
for(int i=0;i<ind;i++){
if(dp[j][i]!=-1)
{
for(int k=0;k<ind;k++)
{
int test=1<<k;
if(j&test)continue;
if(dp[j][i]>=dis[i][k])
{
int nstate=j|test;
dp[nstate][k]=max(dp[nstate][k],dp[j][i]-dis[i][k]);
if(k>=Pn) dp[j|test][k]=mid;
//
int K=(1<<Pn)-1;
if(((j|test)&K)==K)
return true;
}
}
}
}
}
return false;
}
void init(int mid)//預(yù)處理出F到達其他各點最短路
{
memset(v,0,sizeof(v));
memset(dp,-1,sizeof(dp));
queue<node>Q;
//
node t(sx,sy,0);
Q.push(t);
v[sx][sy]=1;
while(!Q.empty())
{
node t=Q.front();Q.pop();
int k=index[t.x][t.y];
if(k!=-1){
if(t.step<=mid)
{
dp[1<<k][k]=mid-t.step;
if(mat[t.x][t.y]==1)
dp[1<<k][k]=mid;
}
}
//
for(int i=0;i<4;i++){
int nx=t.x+dir[i][0];
int ny=t.y+dir[i][1];
if( god(nx,ny) && (!v[nx][ny]) )
{
node nt(nx,ny,t.step+1);
Q.push(nt);
v[nx][ny]=1;
}
}
}
//
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
input();
getIndex();
for(int i=0;i<ind;i++)predo(i);
int l=1;
int r=215;//記得改回來
int ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
init(mid);
if(DP(mid)){
r=mid-1;
ans=mid;
}
else
l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}