《牛客》-E魔法之森的蘑菇（经典BFS变种）

思路：由于某些固定方向的情况，我们将到达该点的粒度划分成从那个方向的到达该点，及基础bfs为每个点可以到达一次，变成没个点可以到达四次（四个方向）用一个三维数组进行标记vis[N][N][4],其余细节看下方ACcode

ACcode:

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define N 1005
#define ll long long

struct node
{
	ll x,y,w,f;
}u;
ll n,m,sx,sy,ex,ey;
int vis[N][N][4];
char a[N][N];

int bfs()
{
	queue<node>q;
	q.push({sx,sy,0,1});
	q.push({sx,sy,0,2});
	q.push({sx,sy,0,3});
	q.push({sx,sy,0,4});
	while(q.size())
	{
		u=q.front();
		q.pop();
		if(u.x<1||u.x>n||u.y<1||u.y>m||vis[u.x][u.y][u.f-1])continue;
		if(a[u.x][u.y]=='#')continue;
		vis[u.x][u.y][u.f-1]=1;
		if(u.x==ex&&u.y==ey)return u.w;
		if(a[u.x][u.y]=='.')
		{
			if(u.f==1)q.push({u.x-1,u.y,u.w+1,u.f});
			if(u.f==2)q.push({u.x,u.y+1,u.w+1,u.f});
			if(u.f==3)q.push({u.x+1,u.y,u.w+1,u.f});
			if(u.f==4)q.push({u.x,u.y-1,u.w+1,u.f});
		}
		if(a[u.x][u.y]=='*')
		{
			if(u.f==1)
			{
				q.push({u.x-1,u.y,u.w+1,1});
				q.push({u.x,u.y+1,u.w+1,2});
				q.push({u.x,u.y-1,u.w+1,4});
			}
			if(u.f==2)
			{
				q.push({u.x-1,u.y,u.w+1,1});
				q.push({u.x,u.y+1,u.w+1,2});
				q.push({u.x+1,u.y,u.w+1,3});
			}
			if(u.f==3)
			{
				q.push({u.x+1,u.y,u.w+1,3});
				q.push({u.x,u.y+1,u.w+1,2});
				q.push({u.x,u.y-1,u.w+1,4});
			}
			if(u.f==4)
			{
				q.push({u.x+1,u.y,u.w+1,3});
				q.push({u.x,u.y-1,u.w+1,4});
				q.push({u.x-1,u.y,u.w+1,1});
			}
		}
	}
	return -1;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int tt=1;
	cin>>tt;
	while(tt--)
	{
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			for(int k=0;k<4;k++)
			{
				vis[i][j][k]=0;
			}
		}
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='S')
			{
				sx=i,sy=j;
				a[i][j]='.';
			}
			else if(a[i][j]=='T')
			{
				ex=i,ey=j;
				a[i][j]='.';
			}
		}
		cout<<bfs()<<endl;
	}
	return 0;
}

over~