2018焦作区域赛 F - Honeycomb Gym - 102028F(BFS)

图看起来很复杂,但是仔细想想其实根本就不用建图,一共六个方向直接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();
}```

上一篇:BFS实现狼羊白菜农夫过河问题


下一篇:HDU - 1253 胜利大逃亡 BFS