蓝桥杯第14届模拟赛最大连通分块(dfs)

news/2024/7/20 22:32:20 标签: 深度优先, 蓝桥杯, 算法

问题描述(答案148)
  小蓝有一个 30 行 60 列的数字矩阵,矩阵中的每个数都是 0 或 1 。
110010000011111110101001001001101010111011011011101001111110
010000000001010001101100000010010110001111100010101100011110
001011101000100011111111111010000010010101010111001000010100
101100001101011101101011011001000110111111010000000110110000
010101100100010000111000100111100110001110111101010011001011
010011011010011110111101111001001001010111110001101000100011
101001011000110100001101011000000110110110100100110111101011
101111000000101000111001100010110000100110001001000101011001
001110111010001011110000001111100001010101001110011010101110
001010101000110001011111001010111111100110000011011111101010
011111100011001110100101001011110011000101011000100111001011
011010001101011110011011111010111110010100101000110111010110
001110000111100100101110001011101010001100010111110111011011
111100001000001100010110101100111001001111100100110000001101
001110010000000111011110000011000010101000111000000110101101
100100011101011111001101001010011111110010111101000010000111
110010100110101100001101111101010011000110101100000110001010
110101101100001110000100010001001010100010110100100001000011
100100000100001101010101001101000101101000000101111110001010
101101011010101000111110110000110100000010011111111100110010
101111000100000100011000010001011111001010010001010110001010
001010001110101010000100010011101001010101101101010111100101
001111110000101100010111111100000100101010000001011101100001
101011110010000010010110000100001010011111100011011000110010
011110010100011101100101111101000001011100001011010001110011
000101000101000010010010110111000010101111001101100110011100
100011100110011111000110011001111100001110110111001001000111
111011000110001000110111011001011110010010010110101000011111
011110011110110110011011001011010000100100101010110000010011
010011110011100101010101111010001001001111101111101110011101
 如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置,则称两个位置连通。与某一个标为 1 的位置连通的所有位置(包括自己)组成一个连通分块。
  请问矩阵中最大的连通分块有多大?
答案提交
  这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

#include<iostream>
#include<algorithm>
using namespace std;
int n, m,res,ans;
char g[65][65];
int dx[]={ 1, 0, -1, 0};
int dy[] = { 0,1,0,-1 };
void dfs(int x, int y)
{

	for (int i = 0; i < 4; i++)
	{
		int a = x + dx[i];
		int b = y + dy[i];
		if (a >= 0 && b >= 0 && a < 30 && b < 60 && g[a][b] == '1')
		{
			res++;
			g[a][b] = '0';
			dfs(a, b);
		}
	}
}
int main()
{
	
	for (int i = 0; i < 30; i++)
		for (int j = 0; j < 60; j++)
			cin >> g[i][j];
	for (int i = 0; i < 30; i++)
		for (int j = 0; j < 60; j++)
		{
			if (g[i][j] == '1') {
				res = 0;
				dfs(i, j);
				ans = max(res, ans);//更新最大值
			}
		}

	cout << ans;
	return 0;
}```


http://www.niftyadmin.cn/n/5442679.html

相关文章

低代码与前端项目部署:革新软件开发的新篇章

随着科技的不断进步&#xff0c;软件开发领域也在经历着前所未有的变革。其中&#xff0c;低代码技术与前端项目部署的结合&#xff0c;为开发者带来了更高效、便捷的开发体验。本文将对低代码与前端项目部署进行深入探讨&#xff0c;分析它们的优势、应用场景以及未来发展趋势…

手机投屏到电脑

手机投屏到电脑 Github 有2个开源的手机投屏项目&#xff1a; Scrcpy: https://github.com/Genymobile/scrcpy QtScrcpy: https://github.com/barry-ran/QtScrcpy 这2个项目都很好用&#xff0c;我这里用的是 Scrcpy&#xff1a; 官方文档中介绍了如何在windows上使用 Scrcpy…

从零开始学习typescript系列4: typescript使用过程中遇到的常见使用场景和常见问题以及解决方案

全局: 如何忽略ts检查 // 单行忽略 // ts-ignore// 忽略全文 // ts-nocheck// 检查全文 // ts-check全局: 如何设置类型声明 目标 projec/types/xxx.d.ts 类型声明文件有效 {"compilerOptions": {"typeRoots": ["./node_modules/types/",…

26-软件定时器

软件定时器 一、什么是软件定时器&#xff1f; 自带的定时器是硬件定时器。 硬件定时器是芯片自身提供的一个功能。一般是通过外部晶振提供给芯片输入时钟&#xff0c;芯片向软件模块提供一组配置的寄存器&#xff0c;通过对寄存器的设置&#xff0c;能够实现定时的功能&…

计算机服务器中了faust勒索病毒怎么办,faust勒索病毒解密工具流程

网络是一把利剑&#xff0c;可以方便企业开展各项工作业务&#xff0c;为企业提供极大的便利&#xff0c;但随着网络技术的不断发展与应用&#xff0c;网络数据安全威胁也在不断增加&#xff0c;给企业的正常生产运营带来了极大困扰&#xff0c;近日&#xff0c;云天数据恢复中…

爬虫案例-网站分词索引与站内搜索

文章目录 1.案例简介2.设计思路3.设计结构4.关键技术5.数据结构6.数据集合7.设计过程7.1 信息采集模块7.2 索引模块7.3 网页排名和搜索 8.示例效果 1.案例简介 本例使用Python建立一个指定网站专用的Web搜索引擎&#xff0c;它能爬取所有指定的网页信息&#xff0c;然后准确的…

nacos 更新报错“发布失败。请检查参数是否正确”

文章目录 &#x1f50a;博主介绍&#x1f964;本文内容起因解决方案结果 &#x1f4e2;文章总结&#x1f4e5;博主目标 &#x1f50a;博主介绍 &#x1f31f;我是廖志伟&#xff0c;一名Java开发工程师、Java领域优质创作者、CSDN博客专家、51CTO专家博主、阿里云专家博主、清华…

leetcode106从中序与后序遍历序列构造二叉树

目录 1.解题关键2.思路3.变量名缩写与英文单词对应关系4.算法思路图解5.代码 本文针对原链接题解的比较晦涩的地方重新进行说明解释 原题解链接&#xff1a;https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solutions/50561/tu-jie-…