#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> using namespace std; int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0}; int vis[44][44];int dis[44][44];int Hash[1111];int Map[44][44];char str[44][44]; int len;int n,m;int Begin; int state[1000]; const int INF=0xfffffff; int dp[1<<17][17]; int Fin; int Ma(int a,int b) { return a>b?a:b; } void bfs(int x,int y) { queue<int > q; q.push(x*m+y); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); vis[x][y]=1;dis[x][y]=0; while(!q.empty()){ int cur=q.front();q.pop(); int xx= cur/m;int yy=cur%m; if(~Hash[cur]){ Map[Hash[x*m+y]][Hash[cur]]= Map[Hash[cur]][Hash[x*m+y]]=dis[xx][yy]; } for(int i=0;i<4;i++){ int x1=xx+dx[i];int y1=yy+dy[i]; if(x1>=0&&x1<n&&y1>=0&&y1<m&&!vis[x1][y1]&&str[x1][y1]!='D'){ vis[x1][y1]=1; dis[x1][y1]=dis[xx][yy]+1; q.push(x1*m+y1); } } } }// 建图 int gao(int mid) { memset(dp,-1,sizeof(dp)); dp[1<<Begin][Begin] = mid; int gg=(1<<len); for(int i=0;i<gg;i++){ for(int j=0;j<len;j++){ if(dp[i][j]==-1) continue; if((i&(1<<j))==0) continue; if((i&Fin)==Fin){ return 1; } for(int k=0;k<len;k++){ if((i&(1<<k))) continue; if(Map[j][k]==-1||dp[i][j]<Map[j][k]) continue; dp[i|(1<<k)][k]=Ma(dp[i|(1<<k)][k],dp[i][j]-Map[j][k]); if(state[k]) dp[i|(1<<k)][k]=mid; } } } return 0; } int main() { while(cin>>n>>m,n||m){ memset(state,0,sizeof(state)); memset(Hash,-1,sizeof(Hash)); memset(Map,-1,sizeof(Map)); Fin = 0;len=0; for(int i=0;i<n;i++){ scanf("%s",str[i]); for(int j=0;j<m;j++){ if(str[i][j]=='S'||str[i][j]=='D') continue; Hash[i*m+j]=len; if(str[i][j]=='F') Begin= len,Fin|=(1<<len); if(str[i][j]=='G') state[len]=1; if(str[i][j]=='Y') Fin|=(1<<len); len++; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++) if(~Hash[i*m+j]){ bfs(i,j); } } int l = 0;int r=n*m+10;int gg=-1; while(l<=r){ int mid= (l+r)>>1; if(gao(mid)){ gg=mid;r=mid-1; } else l=mid+1; } printf("%d ",gg); } return 0; }