10047

#include <iostream>
#include <queue>

#define Green 0
#define Black 1
#define Red 2
#define Blue 3
#define White 4

#define N 0
#define W 1
#define S 2
#define E 3

using namespace std;

struct states{
	int ro,col,wt,direction,wheelcolr;
	};

int m,n,ans;


bool bfs(states src,states trgt,char gr[30][30])
{
	int r,c,d,colr,weight;
	states tmp;
	queue<states> q;
	q.push(src);
	bool visit[30][30][4][5];//r,c,dir,col
	for(int i=0;i<30;i++)
		for(int j=0;j<30;j++)
			for(int k=0;k<4;k++)
				for(int l=0;l<5;l++)
					visit[i][j][k][l]=0;

	while(!q.empty())
	{
		tmp=q.front();q.pop();
		r=tmp.ro; c=tmp.col; d=tmp.direction; colr=tmp.wheelcolr;
		weight=tmp.wt;
		visit[r][d][colr]=true;

		if(r==trgt.ro && c==trgt.col && colr==Green)
		{
			trgt.wt=weight;
			ans=weight;
			return 1;
		}
		if(d==N)
		{
			if(!visit[r][E][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][W][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(r-1>=0 && !visit[r-1][N][(colr+1)%5] && gr[r-1]!='#')
			{
				tmp.ro=r-1; tmp.col=c; tmp.direction=N; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}
		else if(d==S)
		{
			if(!visit[r][E][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][W][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(r+1<m && !visit[r+1][S][(colr+1)%5] && gr[r+1]!='#')
			{
				tmp.ro=r+1; tmp.col=c; tmp.direction=S; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}
		else if(d==W)
		{
			if(!visit[r][N][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][S][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(c-1>=0 && !visit[r][c-1][W][(colr+1)%5] && gr[r][c-1]!='#')
			{
				tmp.ro=r; tmp.col=c-1; tmp.direction=W; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}
		else if(d==E)
		{
			if(!visit[r][N][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][S][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(c+1<n && !visit[r][E][(colr+1)%5] && gr[r]!='#')
			{
				tmp.ro=r; tmp.col=c+1; tmp.direction=E; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}

	}
	return 0;
}
int main()
{
	int kase=1;
	while(cin>>m)
	{
		cin>>n;
		if(m+n==0)
		break;
		states src,trgt;
		char gr[30][30];
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin>>gr[i][j];
				if(gr[i][j]=='S')
				{
					src.ro=i;src.col=j;src.wt=0;
					src.direction=N;src.wheelcolr=Green;
				}
				if(gr[i][j]=='T')
				{
					trgt.ro=i;trgt.col=j;trgt.wt=0;
					trgt.direction=0;trgt.wheelcolr=Green;
				}
			}
		}

		if(kase>1)
			cout<<"\nCase #"<<kase++<<"\n";
		else
			cout<<"Case #"<<kase++<<"\n";
		if(!bfs(src,trgt,gr))
		{
			cout<<"destination not reachable\n";
		}
		else
		{
			cout<<"minimum time = "<<ans<<" sec\n";
		}
	}

	return 0;
}