首页 > 其他分享 >ABC 272 D (BFS)

ABC 272 D (BFS)

时间:2023-02-10 17:23:06浏览次数:47  
标签:cnt ABC ++ BFS int 272 dx dy

ABC 272 D

题意

给定一个N*N的棋盘,棋子初始位置在(1,1),给定一个数M,棋子每步操作可以走到距离不超过M的位置,假设棋子在(i,j),则下一步(x,y)应满足(x-i)×(x-i)+ (y-j)×(y-j)<= M

思路

这是加强版的bfs,平常的bfs一般是四个方向或者八个方向,这次可以有很多个方向,用dx数组和dy数组存储(x,y)。

代码

void make(int i,int k)
{
	dx[++cnt]=i;
	dy[cnt]=k;
	dx[++cnt]=-i;
	dy[cnt]=k;
	dx[++cnt]=i;
	dy[cnt]=-k;
	dx[++cnt]=-i;
	dy[cnt]=-k;
}

void solve()
{
	cin>>n>>m;
	for(int i=0;i*i<=m/2;i++)
	{
		int k=sqrt((m-i*i)*1.0);
		if(k*k!=m-i*i) continue;
		//一对{i,j}有几种情况:{i,j} {-i,j} {i,-j} {-i,-j} 
		//反过来也有
		make(i,k);
		make(k,i);
	}	
	bfs();
	for(int i=1;i<=n;i++) 
	{
		for(int j=1;j<=n;j++)
		{
			cout<<f[i][j]<<" ";
		}
		cout<<endl;
	}
}

标签:cnt,ABC,++,BFS,int,272,dx,dy
From: https://www.cnblogs.com/LIang2003/p/17109732.html

相关文章

  • ABC 281 D
    #AtCoderBeginnerContest281D题意从一个大小为N的数组中选择K个数,使得这K个数的和是D的最大倍数。题解有数据范围1<=K<=N<=100,D<=100可知,这是个简单dp.ntn,m,K......
  • POJ--3669 Meteor Shower(bfs/稍微变通)
    记录21:372023-2-9http://poj.org/problem?id=reference:《挑战程序设计竞赛(第2版)》第二章练习题索引p135DescriptionBessiehearsthatanextraordinarymeteor......
  • 【CCCC】L3-004 肿瘤诊断 (30分),三维BFS
    problemL3-004肿瘤诊断(30分)在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。输入格式:输入第一行给出4个正......
  • CF #724(div2)B. Prinzessin der Verurteilung, BFS枚举
    problemB.PrinzessinderVerurteilungtimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputI,Fischl,Prinz......
  • CF1693 ABCD 题解
    题目链接:https://codeforces.com/contest/1693这场的题都非常好啊……因为现在是从div1开始做了,所以可能刚开始会有点吃力(这场我就会做一个1B呜呜呜)1A先把后缀的极......
  • 电动滑板车UL2272测试报告
    平衡车UL2272测试报告如何办理?平衡车UL测试报告亚马逊平台严格要求提供UL安全测试报告,证明其安全等级,才可以上传亚马逊。UL是美国保险商试验所(UnderwriterLaboratoriesIn......
  • POJ 3126 Prime Path 素数+BFS
    PrimePathTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 27754 Accepted: 15152DescriptionTheministersofthecabinetwerequiteupsetbythem......
  • ABC288 EFG 题解
    E注意到后面选对前面的答案没有影响,而且前面选的顺序对后面的影响是连续的一段(如选2个,那么对应的\(c\)就应该是\(c[i-2..i]\)(对应\(i\)是1、2、3个选时的答案))然......
  • 【230206-3】直角三角形ABC中,C为直角,AC=4,BC=3,E为AC中点,CD垂直AB于D,F为CD、BE交点。求:D
    ......
  • abc288
    C:如果当前连的边和以前连的形成了环,就任意删除一条边,并查集维护。E:首先需要知道,若考虑购买当前物品\(i\),那么设之前买了\(j\)个了,那么可以在\(c_{i-j+1}\simc_i......