首页 > 其他分享 >P4162解题报告

P4162解题报告

时间:2023-12-02 14:22:05浏览次数:37  
标签:node 报告 int nx ny 解题 P4162 105 dis

P4162 解题报告

题意

给你一张 \(n \times m\) 的图,其中 \(a_{i,j}=1\) 表示有障碍,否则没有障碍,其中可以消除 \(t\) 个障碍,求所有格子的最大距离。

分析

这其实就是一道搜索的版子题。

根据数据范围很容易想到可以枚举起点,然后通过广搜遍历起点到每一个点的距离和需要消除障碍的个数。遍历完之后枚举终点,求出消除障碍个数小于 \(t\) 的节点距离起点的最大的距离。

注意,在求最大距离的时候不要先开方,保持精度,等到输出的时候再开方。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int n, m, s, dis[105][105], a[105][105];
double maxn;
struct node{int x, y;};
void bfs(int x, int y){//搜索版子
	queue<node> q;
	q.push((node){x, y});
	dis[x][y] = a[x][y];
	while (!q.empty()){
		node t = q.front();
		q.pop();
		for (int i = 0; i < 4; i++){
			int nx = t.x + dx[i], ny = t.y + dy[i];
			if (nx > 0 && nx <= n && ny > 0 && ny <= m && dis[nx][ny] > dis[t.x][t.y] + (a[nx][ny] == 1)){
				dis[nx][ny] = dis[t.x][t.y] + (a[nx][ny] == 1);//记录需要消除的障碍个数
				q.push((node){nx, ny});
			}
		}
	}
}
signed main(){
	scanf("%lld%lld%lld", &n, &m, &s);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++) scanf("%1lld", &a[i][j]);//这样可以直接一位一位输入整数
	}
	memset(dis, 0x3f, sizeof dis);
	bfs(1, 1);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){//枚举起点
			memset(dis, 0x3f, sizeof dis);
			bfs(i, j);//遍历到每个节点的距离
			for (int k = 1; k <= n; k++){
				for (int l = 1; l <= m; l++){//枚举终点
					if (dis[k][l] <= s) maxn = max(maxn, (double)(k - i) * (k - i) + (l - j) * (l - j));
				}
			} 
		}
	}
	printf("%.6lf", sqrt(maxn));
	return 0;
}

标签:node,报告,int,nx,ny,解题,P4162,105,dis
From: https://www.cnblogs.com/ccf-ioi/p/17871556.html

相关文章

  • 袋鼠云产品功能更新报告08期|近百项全新功能和优化,你要的都在这里!
    欢迎来到袋鼠云08期产品功能更新报告!在瞬息万变的市场环境中,我们深知客户的需求与期待,因此,我们及时推出袋鼠云最新产品更新及优化,包括数据治理中心、HiveSQL性能优化、新插件等,助力企业在数字世界中勇往直前。以下为袋鼠云产品功能更新报告08期内容,更多探索,请继续阅读。离线开发......
  • CMO 2023 P1 解题报告
    \zihao{4}\textbf{Problem:}\large求最小的实数$\lambda$,使得对任意正整数$n$,存在正整数$x_1,x_2,\dots,x_{2023}$,满足$n=x_1x_2\dotsx_{2023}$,且对于$i\in\{1,2,\dots,2023\}$,要么$x_i$为素数,要么$x_i\len^{\lambda}$。\\\zihao{......
  • 软件测试外包公司怎么选择?软件测试报告如何收费?
    随着科技信息的发展,软件产品质量成为企业和用户共同关注话题,因此有效保障软件产品质量的测试手段必不可少。一般为了获取更客观权威的检测报告,企业会将测试工作交由软件测试外包公司进行,也就是专门从事软件测评服务的第三方检测机构。软件测试外包有2种形式可进行:一种是甲......
  • 『Jmeter超级干货』| Linux下Jmeter安装配置、脚本设计执行、监控及报告完整过程
    (『Jmeter超级干货』|Linux下Jmeter安装配置、脚本设计执行、监控及报告完整过程)注意:1、之前写过一个是windows平台的,本文是Linux平台的;2、另外需要注意的是,本文仅为示例过程,所以将客户端和服务器都用在同一台机器上。一般情况下不建议这么做,会影响性能结果的准确性。1JDK......
  • 【专题】从新能源车险看财险经营模式变革报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34418原文出处:拓端数据部落公众号报告合集对中国新能源汽车市场的发展机遇、当前行业状况及未来趋势进行了详细分析。同时,从专业角度分享了海外市场的前沿经验以及中国新能源汽车生态的案例。报告合集总结指出,新能源汽车专属车险的发展和完善不仅......
  • 【专题】2022年中国跨境电商行业研究报告PDF合集分享(附原数据表)
    报告链接:http://tecdat.cn/?p=32044近年来,我国的跨境电子商务发展迅速,在过去五年中,其贸易额增长率达到了16.2%,已经成为稳定对外贸易的一支重要力量。阅读原文,获取专题报告合集全文,解锁文末52份跨境电商行业相关报告。一方面,随着跨境电子商务的发展,跨境电子商务的监管政策得到了......
  • 原语科技案例入选《2023全球隐私计算报告》
    在这个数字化迅速发展的时代,隐私计算作为保护数据安全的重要技术,正受到全球范围内越来越多的关注。11月23日,第二届全球数字贸易博览会在杭州国际博览中心隆重举行。来源:《2023全球隐私计算报告》报告亮点国内外频繁出台的隐私计算相关政策国际上今年发生的隐私计算相关动......
  • 【专题】2022汽车品牌影响力研究报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34404原文出处:拓端数据部落公众号近年来,汽车市场中的品牌销量排名发生了巨大的变化,形成了比亚迪和大众两大巨头。比亚迪在中国品牌中的销量增长迅速,特别是在新能源领域,引领着中国品牌的快速增长。豪华品牌方面,形成了一个由BBA和特斯拉组成的新一......
  • 今日报告
    今天完成了软甲构造的实验一,利用百度ai进行汉译英,英译汉的翻译,还完成了人机交互的作业汇总,人机交互这周就结课了。今天在人机交互大作业时,利用flash制作动画,并运用到网页上,下载了很多flash,最终都不能用,最后还是下载了flash8.0,制作了一个较为简单的开灯关灯的动画。......
  • Linux第十四周学习报告
    网络管理    如果我们要用xshall连接我们的虚拟机,那么我们需要静态的ip地址,查看ip地址使用ipconfig命令(win+rcmd)。Linux操作系统提供了强大的网络功能,它提供了许多完善的网络工具来配置网络。用户既可以通过命令行的方式,也可以通过直接修改配置文件轻松完成网络配......