双向广搜

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

struct node{
int x,y,step;
};
int n,m,sx,sy,fx,fy,ax[5] = {0,1,-1,0,0},ay[5] = {0,0,0,1,-1};
queue<node> qu[2];
vector<vector<int> > ans;
vector<vector<char> > mp;
vector<vector<bool> > vis[2];
void input(){
cin >> n >> m;
ans.resize(n + 5,vector<int>(m + 5,0)),mp.resize(n + 5,vector<char>(m + 5,' '));
vis[0].resize(n + 5,vector<bool>(m + 5,0)),vis[1].resize(n + 5,vector<bool>(m + 5,0));
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin >> mp[i][j];
if(mp[i][j] == 'S') sx = i,sy = j;
if(mp[i][j] == 'T') fx = i,fy = j;
}
}
}
bool check(int nx,int ny){
if(nx < 1 || ny < 1 || nx > n || ny > m) return 1;
return 0;
}
void bfs(){
qu[0].push({sx,sy,0}),qu[1].push({fx,fy,0});
int flag = 0;
vis[0][sx][sy] = 1,vis[1][fx][fy] = 1;
while(!qu[0].empty() && !qu[1].empty()){
queue<node> &q = qu[flag];
int o_flag = (flag + 1) % 2;
node r = q.front();
q.pop();

	if(vis[o_flag][r.x][r.y]){
		cout << r.step + ans[r.x][r.y];
		return ;
	}
	for(int i = 1;i <= 4;i++){
		int nx = r.x + ax[i],ny = r.y + ay[i];
		if(check(nx,ny) || vis[flag][nx][ny] || mp[nx][ny] == '#') continue;
		q.push({nx,ny,r.step + 1});
		vis[flag][nx][ny] = 1;
		ans[nx][ny] = r.step + 1;
	}
	flag = o_flag;
}
cout << -1;

}
int main(){
input();
bfs();
return 0;
}