求助
查看原帖
求助
548568
宙空Starsky楼主2022/7/25 21:07
#include<bits/stdc++.h>
using namespace std;
struct Tnode{
	int x,y;
	int step;
} qu[401];
int dx[12]={1,2,2,1,-1,-2,-2,-1,2,2,-2,-2};
int dy[12]={2,1,-1,-2,-2,-1,1,2,2,-2,-2,2};
int a[21][21];
int BFS(int x0,int y0){
	qu[0].x=1;
	qu[0].y=1;
	a[1][1]=0;
	int head=0;
	int tail=1;
	while(head<tail)
	{
		int x=qu[head].x;
		int y=qu[head].y;
		int s=qu[head].step+1;
		head++;
		for(int d=0;d<12;d++)
		{
			int nx=x+dx[d];
			int ny=y+dy[d];
			if(a[nx][ny]==1)
			{
				if(nx==x0&&ny==y0)
				{
					return s+1;
				}
				qu[tail].x=nx;
				qu[tail].y=ny;
				qu[tail++].step=s+1;
				a[nx][ny]=0;
			}
		}
	}
	return qu[tail].step-1;
}
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		while(ch=='-')
		{
			w*=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s*w;
}
int main(){
	int x1=read(),y1=read(),x2=read(),y2=read();
	for(int i=1;i<=20;i++)
	{
		for(int j=1;j<=20;j++)
		{
			a[i][j]=1;
		}
	}
	cout<<BFS(x1,y1)<<endl;
	for(int i=1;i<=20;i++)
	{
		for(int j=1;j<=20;j++)
		{
			a[i][j]=1;
		}
	}
	memset(qu,1,sizeof(qu));
	cout<<BFS(x2,y2);
	return 0;
}
2022/7/25 21:07
加载中...