图看起来很复杂,但是仔细想想其实根本就不用建图,一共六个方向直接bfs就行,具体见代码。
AC代码:
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5010,M=7010;
typedef pair<int,int> PII;
PII St,ed;
int n,m;
char g[N][M];
int dx[6]={2,2,-2,-2,4,-4};
int dy[6]={-6,6,-6,6,0,0};
int nx[6]={1,1,-1,-1,2,-2};
int ny[6]={-3,3,-3,3,0,0};
struct node{
int x,y,dist;
};
queue<node>q;
void solve(){
cin>>n>>m;
for(int i=0;i<=4*n+10;i++)
for(int j=0;j<=6*m+10;j++)
g[i][j]=' ';
getchar();
for(int i=1;i<=4*n+3;i++) {
gets(g[i] + 1);
}
for(int i=1;i<=4*n+3;i++)
for(int j=1;j<=6*m+3;j++)
if(g[i][j]=='S') St={i,j};
else if(g[i][j]=='T')ed={i,j};
while(q.size()) q.pop();
q.push({St.x,St.y,0});
int res=-1;
while(q.size()){
auto t=q.front();
q.pop();
for(int i=0;i<6;i++){
int a=t.x+dx[i],b=t.y+dy[i],dist=t.dist+1;
int aa=t.x+nx[i],bb=t.y+ny[i];
if(a<1||a>4*n+3||b<1||b>6*m+3)continue;
if(g[aa][bb]!=' '||g[a][b]=='@')continue;
g[a][b]='@';
if(a==ed.x&&b==ed.y){
cout<<dist+1<<endl;
return;
}
q.push({a,b,dist});
}
}
cout<<res<<endl;
}
main(){
int T;
cin>>T;
while(T--)solve();
}```