#include <iostream>
#include <string>
#include <queue>
#include <memory>
using namespace std;
int col,row;
char tem[100];
char map[100][100];
bool used[100][100][2];
int min;
int temx1,temy1;
queue <int> q;
int temx,temy,time,foot;
int dir1[9][2]={{0,1},{-1,1},{-2,1},{1,1},{2,1},{0,2},{-1,2},{1,2},{0,3}};
int dir2[9][9]={{0,-1},{-1,-1},{-2,-1},{1,-1},{2,-1},{0,-2},{-1,-2},{1,-2},{0,-3}};
bool proper(int x,int y )
{
	if(x>=0 && x<row && y>=0 && y<col && map[x][y]!='X')
		return true;
	return false;
}
int main()
{
	int i,j,k;
	while(cin>>col>>row&&(row||col))
	{
		gets(tem);
		for(i=0;i<row;i++)
		{
			gets(tem);
			k=0;
			for(j=0;j<strlen(tem);j++)
				if(tem[j]!=' ')
					map[i][k++]=tem[j];
		}
		while(!q.empty())
			q.pop();
		memset(used,0,sizeof(used));
		for(j=0;j<col;j++)
			if(map[row-1][j]=='S')
			{
				q.push(row-1);
				q.push(j);
				q.push(0);
				q.push(0);
				q.push(row-1);
				q.push(j);
				q.push(0);
				q.push(1);
				used[row-1][j][0]=true;
				used[row-1][j][1]=true;
			}
		min=999999;
		
		while(!q.empty())
		{
			temx1=q.front(); q.pop();
			temy1=q.front(); q.pop();
			time=q.front(); q.pop();
			foot=q.front(); q.pop();
			if(foot==0)
			{
				for(i=0;i<9;i++)
				{
					temx=temx1+dir1[i][0];
					temy=temy1+dir1[i][1];
					if(proper(temx,temy))
					{
						if(map[temx][temy]=='T')
						{
							if(time<min) min=time;
							continue;
						}
						else if(!used[temx][temy][1])
							{
								q.push(temx);
								q.push(temy);
							    q.push(time+map[temx][temy]-'0');
								q.push(1-foot);
								used[temx][temy][1]=true;
							}
					}
				}
			}//left foot
			else if(foot==1)
			{
				for(i=0;i<9;i++)
				{
					temx=temx1+dir2[i][0];
					temy=temy1+dir2[i][1];
					if(proper(temx,temy))
					{
						if(map[temx][temy]=='T')
						{
							if(time<min) min=time;
							continue;
						}
					
						else if(!used[temx][temy][0])
							{
								q.push(temx);
								q.push(temy);
								q.push(time+map[temx][temy]-'0');
								q.push(1-foot);
								used[temx][temy][0]=true;
							}
					}
				}
			}//right foot
		}//while
		if(min==999999) cout<<-1<<endl;
		else cout<<min<<endl;
		//cout<<"----------------------------------"<<endl;
	}
	return 0;
}
				

• Re:这明显的DFS，为什么我连Sample都过不了，小牛们闲来没事儿进来看看哈 (18) dongshanluo 2007-08-07 17:12:07
  • Re:这明显的DFS，为什么我连Sample都过不了，小牛们闲来没事儿进来看看哈 (30) limingfei 2007-08-07 21:53:54
    • Re:这明显的DFS，为什么我连Sample都过不了，小牛们闲来没事儿进来看看哈 (16) xiaox 2007-08-07 22:08:03