求助,80分T两个
  • 板块P1443 马的遍历
  • 楼主Qwdb
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/7/24 10:35
  • 上次更新2023/11/4 13:29:15
查看原帖
求助,80分T两个
122235
Qwdb楼主2021/7/24 10:35
#include<bits/stdc++.h>
using namespace std;
const int N=405;
int n,m,x,y;
int head,tail,book[N][N];
int ans[405][405]={N*N};
int q[3][2*N*N],fx[8][2]={{1,-2},{1,2},{2,1},{2,-1},{-1,-2},{-1,2},{-2,-1},{-2,1}};
void bfs(int x,int y)
{
	while(head<=tail)
	{
		if(q[0][head]==x && q[1][head]==y)
		{
			ans[x][y]=min(ans[x][y],q[2][head]);
			break;
		}
		for(int i=0;i<8;i++)
		{
			int vx=q[0][head]+fx[i][0],vy=q[1][head]+fx[i][1];
			if(vx>=1 && vx<=n && vy>=1 && vy<=m && book[vx][vy]==0)
			{
				q[0][tail]=vx;
				q[1][tail]=vy;
				q[2][tail]=q[2][head]+1;
				book[vx][vy]=1;
				tail++;
			}
		}
		head++;
	}
	return;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&x,&y);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans[i][j]=99999999;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			head=1;
			tail=2;
			q[0][1]=x;
			q[1][1]=y;
			q[2][1]=0;
			memset(book,0,sizeof(book));
			bfs(i,j);
			if(ans[i][j]==99999999)
				printf("-1   ");
			else
				printf("%-5d",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
} 
2021/7/24 10:35
加载中...