省赛选拔时的一道题目。当时看到20维就晕晕的。其实只要把它缩成一维，在最短路就可以了
#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
#include"queue"
#define INF 10000000 ;
using namespace std;
int vex[1048576+100];
struct Node
{
int u,v,next;
}arc[1048576+100];
char vis[1048576+100];
int dis[1048576];
int n[25],m,nn[20],d;
char a[1048576+100];
int ii[25],T,M,S,ep;
void add(int u,int v)
{
arc[ep].u=u;arc[ep].v=v;
arc[ep].next=vex[u];
vex[u]=ep++;
}
void ADD(int u,int v)
{
add(u,v);
add(v,u);
}
void init()
{
nn[0]=1;ep=0;
memset(vex,-1,sizeof(vex));
for(int i=1;i<d;i++)
nn[i]=n[i-1]*nn[i-1];
m=n[d-1]*nn[d-1];
m=m/n[0];
memset(vis,-1,sizeof(vis));
memset(ii,0,sizeof(ii));
}
void build_G()
{
int x=0;
for(int i=0;i<m;i++)
{
scanf("%s",a);
for(ii[0]=0;ii[0]<n[0];ii[0]++){
if(a[ii[0]]!='#')
{
for(int k=0;k<d;k++){
if(ii[k]>0&&vis[x-nn[k]]==0)
ADD(x,x-nn[k]);
}
if(a[ii[0]]=='T') T=x;
else if(a[ii[0]]=='M') M=x;
else if(a[ii[0]]=='S') S=x;
vis[x]=0;
}
x++;
}
ii[1]++;
for(int j=1;j<d;j++){
ii[j+1]+=ii[j]/n[j];
ii[j]=ii[j]%n[j];
}
}
m=x;
}
int Spfa(int s,int t)
{
queue<int> q;
for(int i=0;i<m;i++) dis[i]=INF;
dis[s]=0;
q.push(s);vis[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=vex[u];i!=-1;i=arc[i].next){
int v=arc[i].v;
if(dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
vis[u]=0;
}
return dis[t];
}
int solve()
{
int s=0;
vis[M]=1;
s=Spfa(T,S);
memset(vis,0,sizeof(vis));
s+=Spfa(M,T);
s+=dis[S];//cout<<s<<endl;
if(s>=10000000) return -1;
return s;
}
int main()
{
while(cin>>d)
{
if(!d) break;
for(int i=0;i<d;i++)
scanf("%d",&n[i]);
init();
build_G();//printf("ep=%d\n",ep);
int sd=solve();
if(sd==-1)
printf("No solution. Poor Theseus!\n");
else
printf("Theseus needs %d steps.\n",sd);
}
return 0;
}