#include<iostream>#include<cstring>#include<algorithm>#include<cstdlib>#include<map>#include<cstdio>#include<vector>#include<utility>#include<queue>using namespace std;char str[55],G[3000][50][50],NOW;int x[50],y[50],n,m,st=0,ed=6,p=0;int dis[3000][50][50];bool vist[50][50],vis[7];int selects[7];int last[3000],cnt,q;vector<pair<int,int> > lastMap[3000];map<string,int> msi;bool jud(int x,int y){ if(x<1 ||x>n||y<1||y>m) return false; return true;}void bfs1(int cur,int x,int y,int dist){ queue<pair<int,int> > que; vist[x][y]=1; dis[cur][x][y]=dist; que.push(make_pair(x,y)); while(!que.empty()){ pair<int ,int> pii=que.front(); que.pop(); int xx=pii.first,yy=pii.second; if(G[cur][xx][yy]=='Y'||G[cur][xx][yy]=='G'||G[cur][xx][yy]=='*'){ dis[cur][xx][yy]=-1; continue; } if(G[cur][xx][yy]=='y'||G[cur][xx][yy]=='g') continue; if(!vist[xx+1][yy]&&jud(xx+1,yy)){ dis[cur][xx+1][yy]=dis[cur][xx][yy]+1; que.push(make_pair(xx+1,yy)); vist[xx+1][yy]=1; } if(!vist[xx-1][yy]&&jud(xx-1,yy)){ dis[cur][xx-1][yy]=dis[cur][xx][yy]+1; que.push(make_pair(xx-1,yy)); vist[xx-1][yy]=1; } if(!vist[xx][yy+1]&&jud(xx,yy+1)){ dis[cur][xx][yy+1]=dis[cur][xx][yy]+1; que.push(make_pair(xx,yy+1)); vist[xx][yy+1]=1; } if(!vist[xx][yy-1]&&jud(xx,yy-1)){ dis[cur][xx][yy-1]=dis[cur][xx][yy]+1; que.push(make_pair(xx,yy-1)); vist[xx][yy-1]=1; } }}void dfs2(int cur,int x,int y){ vist[x][y]=1; if(G[cur][x][y]=='*') return; if(G[cur][x][y]=='Y'||G[cur][x][y]=='G') if(G[cur][x][y]!=NOW) return; if(G[cur][x][y]==NOW){ G[cur][x][y]='.'; return; } if(!vist[x+1][y]&&jud(x+1,y)) dfs2(cur,x+1,y); if(!vist[x-1][y]&&jud(x-1,y)) dfs2(cur,x-1,y); if(!vist[x][y-1]&&jud(x,y-1)) dfs2(cur,x,y-1); if(!vist[x][y+1]&&jud(x,y+1)) dfs2(cur,x,y+1);}void generates(){ int pre=0; for(int i=0;i<cnt;i++){ string s=""; for(int j=0;j<=i;j++) s=s+char(selects[j]+'0'); if(msi.count(s)!=0){ pre=msi[s]; continue; } ++q; last[q]=selects[i]; int xx=x[last[q]],yy=y[last[q]]; if(dis[pre][xx][yy]==-1){ q--; break; } lastMap[pre].push_back(make_pair(q,dis[pre][xx][yy])); memset(dis[q],-1,sizeof(dis[q])); memcpy(G[q],G[pre],sizeof(G[q])); memset(vist,0,sizeof(vist)); NOW=G[0][xx][yy]-32; G[q][xx][yy]='.'; dfs2(q,xx,yy); memset(vist,0,sizeof(vist)); bfs1(q,xx,yy,0); pre=q; msi[s]=q; }}void getSeq(int sel){ if(sel==cnt){ generates(); } else{ for(int i=1;i<=cnt;i++){ if(vis[i]) continue; vis[i]=1; selects[sel]=i; getSeq(sel+1); vis[i]=0; } }}int ret;void dfs(int u,int d){ if(u==q+1){ ret=min(ret,d); return; } for(int i=0;i<lastMap[u].size();i++){ int v=lastMap[u][i].first; int c=lastMap[u][i].second; dfs(v,c+d); }}void solve(){ q=0; msi.clear(); for(int i=0;i<3000;i++) lastMap[i].clear(); memset(dis[0],-1,sizeof(dis[0])); memset(vist,0,sizeof(vist)); bfs1(0,x[st],y[st],0); memset(vis,0,sizeof(vis)); getSeq(0); for(int i=0;i<=q;i++) if(dis[i][x[ed]][y[ed]]!=-1) lastMap[i].push_back(make_pair(q+1,dis[i][x[ed]][y[ed]])); ret=0x3f3f3f3f; dfs(0,0); if(ret==0x3f3f3f3f) printf("-1n"); else printf("%dn",ret);}int main(){ while(~scanf("%d%d",&n,&m)){ p=0;cnt=0; for(int i=1;i<=n;i++){ scanf("%s",str); for(int j=0;j<strlen(str);j++){ G[0][i][j+1]=str[j]; if(G[0][i][j+1]=='s') x[st]=i,y[st]=j+1; else if(G[0][i][j+1]=='e') x[ed]=i,y[ed]=j+1; else if(G[0][i][j+1]=='y' || G[0][i][j+1]=='g') x[p+1]=i,y[++p]=j+1,cnt++; } } solve(); } return 0;}
