P1443求助 AC90 TLE10
  • 板块题目总版
  • 楼主var_phi
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/10/6 10:41
  • 上次更新2023/11/4 04:38:11
查看原帖
P1443求助 AC90 TLE10
444690
var_phi楼主2021/10/6 10:41

#include <bits/stdc++.h>
using namespace std;
int n,m,y,x,ans,nx,ny,p;
int a[405][405];
int f[405][405];
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={2,1,-1,-2,2,1,-1,-2};
struct Node{
	int x;int y;
}s;
queue<Node> q;
vector<Node> v;
bool flag=0;
void bfs(int x,int y,int N)
{
	while (!q.empty())
	{
		Node now=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			nx=now.x+dx[i];ny=now.y+dy[i];
			if(nx<=n&&nx>=1&&ny<=m&&ny>=1&&(f[nx][ny]==0||N<a[nx][ny]))
			{
				Node pos;
				pos.x=nx;pos.y=ny;q.push(pos);
				a[nx][ny]=N;
				f[nx][ny]=1;
				bfs(nx,ny,N+1);
			}
		}
		
	}
}
int main()
{
	for(int i=1;i<405;i++)
		for(int j=1;j<405;j++)
			a[i][j]=114514;
	scanf("%d%d%d%d",&n,&m,&x,&y);
	for (int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(i==x&&j==y)
			{
				s.x=i;s.y=j;
				a[x][y]=0;
				//printf("%d %d\n",i,j);
				f[x][y]=1;
				q.push(s);
			}
		}
	bfs(s.x,s.y,1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==114514)
				printf("%-5d",-1);
			else{
				printf("%-5d",a[i][j]);
			}
			
		}
		printf("\n");
	}		
	//printf("\n%d",ans);
	return 0;
 } 
2021/10/6 10:41
加载中...