C++14(g++5.4) 解法, 执行用时: 415ms, 内存消耗: 24060K, 提交时间: 2020-01-10 15:42:52

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e3+10;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,sx,sy,ex,ey,vis[N][N]; char g[N][N];
void bfs(){
	queue<pair<int,int> > q; q.push({sx,sy}); memset(vis,-1,sizeof vis); vis[sx][sy]=0;
	while(q.size()){
		int x=q.front().first,y=q.front().second;	q.pop();
		for(int i=0;i<4;i++){
			int tx=x+dx[i],ty=y+dy[i];
			while(tx>=1&&tx<=n&&ty>=1&&ty<=m&&g[tx][ty]!='*'){
				if(vis[tx][ty]==-1)	vis[tx][ty]=vis[x][y]+1,q.push({tx,ty});
				if(tx==ex&&ty==ey)	return ;
				tx+=dx[i],ty+=dy[i];
			}				
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	scanf("%s",g[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(g[i][j]=='S')	sx=i,sy=j;
			if(g[i][j]=='T')	ex=i,ey=j;
		}
	bfs();
	if(vis[ex][ey]==-1)	puts("troil");
	else	cout<<vis[ex][ey]-1;
	return 0;
}

C++ 解法, 执行用时: 307ms, 内存消耗: 20160K, 提交时间: 2021-07-15 11:30:41

#include<bits/stdc++.h>

using namespace std;
const int N=2e3+10;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,sx,sy,ex,ey,vis[N][N]; char g[N][N];
void bfs(){
	queue<pair<int,int> > q; q.push({sx,sy}); memset(vis,-1,sizeof vis); vis[sx][sy]=0;
	while(q.size()){
		int x=q.front().first,y=q.front().second;	q.pop();
		for(int i=0;i<4;i++){
			int tx=x+dx[i],ty=y+dy[i];
			while(tx>=1&&tx<=n&&ty>=1&&ty<=m&&g[tx][ty]!='*'){
				if(vis[tx][ty]==-1)	vis[tx][ty]=vis[x][y]+1,q.push({tx,ty});
				if(tx==ex&&ty==ey)	return ;
				tx+=dx[i],ty+=dy[i];
			}				
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	scanf("%s",g[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(g[i][j]=='S')	sx=i,sy=j;
			if(g[i][j]=='T')	ex=i,ey=j;
		}
	bfs();
	if(vis[ex][ey]==-1)	puts("troil");
	else	cout<<vis[ex][ey]-1;
	return 0;
}