当你敲了一坨dfs却……
查看原帖
当你敲了一坨dfs却……
1461766
JNOI2427楼主2024/9/19 11:05

错误示范(错哪了!!我不理解!!):

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
bool vis[105][105]={false};
int n,m,r,zb[105][105]={0};
int dx[5]={0,1,0,-1};
int dy[5]={1,0,-1,0};
int a,b;
bool check(int x,int y)
{
	if(x<1||x>n||y<1||y>n) return false;
	return true;
}
void dfs(int x,int y)
{	
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(check(nx,ny)&&!vis[nx][ny]&&sqrt((nx-a)*(nx-a)+(ny-b)*(ny-b))<=r)
		{
			vis[nx][ny]=true;
			zb[nx][ny]=1;
			dfs(nx,ny);
		}	
	}
}
int main()
{
	cin>>n>>m>>r;	
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		if(!vis[a][b])
		{
			zb[a][b]=1;
		}
		dfs(a,b);
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(zb[i][j]==1) cnt++;
		}
	}
	cout<<cnt;	
	return 0;
}

正解:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,r,a[105][105]={0};
	cin>>n>>m>>r;
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(sqrt((x-i)*(x-i)+(y-j)*(y-j))<=r) a[i][j]=1;
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]==1) cnt++;
		}
	}
	cout<<cnt;
	return 0;
}

却败给了暴力枚举……

2024/9/19 11:05
加载中...