C++14(g++5.4) 解法, 执行用时: 504ms, 内存消耗: 37904K, 提交时间: 2019-01-28 14:26:16

#include<iostream>
#include<queue>
using namespace std;
const int L=6500;
char mp[L][L];
int n,m;
struct node{
	int x,y,s;
};
int main(){
	int next[2][4]={1,0,-1,0,0,1,0,-1};
	queue<node>q;
	cin>>n>>m;
	n=2*n+1;m=2*m+1;
	getchar();
	for(int i=0;i<n;i++){
		getchar();//接受每次每行的换行字符； 
		for(int j=0;j<m;j++){
			mp[i][j]=getchar();
		}
	}
	int stx,sty,flag=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(mp[i][j]=='S'){
				stx=i;sty=j;
			}
			if(mp[i][j]!='S'&&mp[i][j]!='T'&&mp[i][j]!=' ')mp[i][j]='#';
		}
	}
	q.push(node{stx,sty,1}); 
	while(!q.empty()){
		node h=q.front();q.pop();
		for(int i=0;i<4;i++){
			int tx=h.x+next[0][i];
			int ty=h.y+next[1][i];
			if(mp[tx][ty]=='#'||tx<0||ty<0||tx>=n||ty>=m)continue;
			mp[tx][ty]='#';
			tx+=next[0][i];
			ty+=next[1][i];
			q.push(node{tx,ty,h.s+1});
		    if(mp[tx][ty]=='T'){
		    	cout<<h.s+1<<endl;
		    	return 0;
			}
		}
	}
	cout<<"TRDD Got lost...TAT"<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 554ms, 内存消耗: 46456K, 提交时间: 2020-02-27 13:37:03

#include<bits/stdc++.h>
using namespace std;
int d[4][2]={1,0,0,1,-1,0,0,-1};
string mp[6005];
bool vis[6005][6005];
int n,m;
struct edge
{
	int x,y;
	int d;
};
queue<edge>q;
int main()
{
	ios_base::sync_with_stdio(0);
	cin>>n>>m;
	n=n*2+1;
	m=m*2+1;
	int sx,sy;
	getchar();
	for(int i=0;i<n;i++)
	{
		getline(cin,mp[i]);
		for(int j=0;j<m;j++)
		if(mp[i][j]=='S') sx=i,sy=j;
	}
	int ans=-1;
	q.push(edge{sx,sy,1});
	vis[sx][sy]=1;
	while(q.size())
	{
		edge u=q.front();
		q.pop();
		for(int k=0;k<4;k++)
		{
			int x=u.x+d[k][0];
			int y=u.y+d[k][1];
			if(mp[x][y]!=' '&&mp[x][y]!='T') continue;
			if(vis[x][y]) continue;
			if(mp[x][y]=='T') ans=u.d+1;
			q.push(edge{x,y,u.d+1});
			vis[x][y]=1;
		}
		if(ans!=-1) break;
	}
	if(ans!=-1) cout<<ans/2+1<<endl;
	else cout<<"TRDD Got lost...TAT"<<endl;
}