萌新求助bfs
查看原帖
萌新求助bfs
547609
QZY2008楼主2021/9/27 22:59

本人初学BFS

过不了样例代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=401;
struct Node{
	ll x,y;
	ll step;
};
Node q[N*N];
ll n,m;
ll b1,b2;
ll e1,e2;
ll g[N][N];
ll ans[N][N];
const ll dx[8]={-1,-2,-2,-1,1,2,2,1};
const ll dy[8]={2,1,-1,-2,2,1,-1,-2};
inline bool check(ll x,ll y){
	if (x<=n&&y<=m&&x>=1&&y>=1&&g[x][y]==0)
		return true;
	return false;
}
inline ll bfs(){
	ll head=0;
	ll tail=1;
	q[tail].x=b1;q[tail].y=b2;q[tail].step=0;
	g[b1][b2]=1;
	while (head!=tail){
		head++;
		for (ll i=0;i<8;i++){
			ll n1=q[head].x+dx[i],n2=q[head].y+dy[i];
			if (check(n1,n2)){
				q[++tail].x=n1;q[tail].y=n2;
				q[tail].step=q[head].step+1;
				g[n1][n2]=1;
				if (q[tail].x==e1&&q[tail].y==e2)
					return q[tail].step;
			}
		}
	}
	return -1;
} 
int main(){
	scanf("%lld%lld",&n,&m);
	scanf("%lld%lld",&b1,&b2);
	for (ll i=1;i<=n;i++)	
		for (ll j=1;j<=m;j++)
			e1=i,e2=j,ans[i][j]=bfs();
	for (ll i=1;i<=n;i++,puts(""))
		for (ll j=1;j<=m;j++)
			printf("%lld     ",ans[i][j]);
}
2021/9/27 22:59
加载中...