蒟蒻求助:TLE*7,DFS,已加阀值
查看原帖
蒟蒻求助:TLE*7,DFS,已加阀值
421773
unsigned_char楼主2021/2/24 21:30

蒟蒻不会BFS,DFS加阀值仍TLE。评测记录

#include<iostream>
#include<cstdio>
using namespace std;

int ans[410][410];
int n,m;
int sx,sy;

void search(int x,int y,int sum)
{
	if(sum>100)
	{
		return;
	}
	if(x<1||x>n||y<1||y>m)
	{
		return;
	}
	if((sum>ans[x][y]&&ans[x][y]!=0)||(x==sx&&y==sy))
	{
		return;
	}
	ans[x][y]=sum;
	search(x+2,y+1,sum+1);
	search(x-2,y+1,sum+1);
	search(x+2,y-1,sum+1);
	search(x-2,y-1,sum+1);
	search(x+1,y+2,sum+1);
	search(x-1,y+2,sum+1);
	search(x+1,y-2,sum+1);
	search(x-1,y-2,sum+1);
	return;
}

int main()
{
	scanf("%d%d",&n,&m);
	scanf("%d%d",&sx,&sy);
	search(sx+2,sy+1,1);
	search(sx-2,sy+1,1);
	search(sx+2,sy-1,1);
	search(sx-2,sy-1,1);
	search(sx+1,sy+2,1);
	search(sx-1,sy+2,1);
	search(sx+1,sy-2,1);
	search(sx-1,sy-2,1);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(i==sx&&j==sy)
			{
				printf("%-5d",0);
				continue;
			}
			if(ans[i][j]==0)
			{
				printf("%-5d",-1);
				continue;
			}
			printf("%-5d",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}
2021/2/24 21:30
加载中...