1335:【例2-4】连通块

简介: 1335:【例2-4】连通块

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

一个n × m的方格图,一些格子被涂成了黑色,在方格图中被标为1,白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域,其中的每个黑色格子能通过四连通的走法(上下左右),只走黑色格子,到达该联通块中的其它黑色格子。

【输入】

第一行两个整数n,m(1≤n,m≤100),表示一个n × m的方格图。

接下来n行,每行m个整数,分别为0或1,表示这个格子是黑色还是白色。

【输出】

一行一个整数ans,表示图中有ans个黑色格子连通块。

【输入样例】

3 3

1 1 1

0 1 0

1 0 1

【输出样例】

3

1. #include<iostream>
2. #include<stdio.h>
3. #include<cmath>
4. #include<cstring>
5. #include<list>
6. using namespace std;
7. int map[105][105];
8. int que[15010][2];
9. int xy_[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
10. int n,m,tj=0;
11. int main()
12. {
13.   scanf("%d %d",&n,&m);
14.   for(int i=1;i<=n;i++) 
15.     for(int j=1;j<=m;j++)
16.       scanf("%d",&map[i][j]);
17.   for(int i=1;i<=n;i++) 
18.     for(int j=1;j<=m;j++){
19.       if(map[i][j]){
20.         tj++;
21.         int top=0;
22.         int tail=0;
23.         memset(que,0,sizeof(que));
24.         que[tail][0]=i;que[tail][1]=j;tail++;
25.         while(tail>top){
26.           int x=que[top][0],y=que[top][1];top++;
27.           for(int k=0;k<4;k++){
28.             if(map[x+xy_[k][0]][y+xy_[k][1]]){
29.               que[tail][0]=x+xy_[k][0];
30.               que[tail][1]=y+xy_[k][1];
31.               tail++;
32.             }
33.           }
34.           map[x][y]=0;
35.         } 
36.       }
37.     }
38.   cout<<tj<<endl;
39.   return 0;
40.  }


相关文章
|
7月前
|
SQL 关系型数据库 MySQL
【Go语言专栏】使用Go语言连接MySQL数据库
【4月更文挑战第30天】本文介绍了如何使用Go语言连接和操作MySQL数据库,包括选择`go-sql-driver/mysql`驱动、安装导入、建立连接、执行SQL查询、插入/更新/删除操作、事务处理以及性能优化和最佳实践。通过示例代码,展示了连接数据库、使用连接池、事务管理和性能调优的方法,帮助开发者构建高效、稳定的Web应用。
1346 0
|
人工智能
天梯赛-L1-064 估值一亿的AI核心代码 (20 分)--2019全国CCCC天梯赛L1题解
天梯赛-L1-064 估值一亿的AI核心代码 (20 分)--2019全国CCCC天梯赛L1题解
373 0
|
网络虚拟化 网络架构
三层交换机的详细配置步骤
三层交换机的详细配置步骤 1、三层交换机 三层交换机就是具有部分路由器功能的交换机,工作在OSI网络标准模型的第三层:网络层。三层交换机的最重要目的是加快大型局域网内部的数据交换,所具有的路由功能也是为这目的服务的,能够做到一次路由,多次转发。
2815 0
|
7月前
|
JavaScript 前端开发 API
Vue3 组合式 API 的特性、用法和最佳实践
Vue3 组合式 API 的特性、用法和最佳实践
295 1
|
关系型数据库 数据库 PostgreSQL
Diesel框架对于数据库的使用和实战,在PostgreSQL的基础上的使用【Diesel】
Diesel框架对于数据库的使用和实战,在PostgreSQL的基础上的使用【Diesel】
291 0
|
7月前
|
机器学习/深度学习 分布式计算 搜索推荐
【大数据技术】Spark MLlib机器学习协同过滤电影推荐实战(附源码和数据集)
【大数据技术】Spark MLlib机器学习协同过滤电影推荐实战(附源码和数据集)
272 0
|
API
OpenCV_05 形态学操作:连通性+腐蚀和膨胀+开闭运算+礼帽和黑帽
在图像中,最小的单位是像素,每个像素周围有8个邻接像素,常见的邻接关系有3种:4邻接、8邻接和D邻接。
327 0
|
机器学习/深度学习 数据采集 人工智能
基于深度学习设计AI麻将程序
基于深度学习设计AI麻将程序
1787 0
基于深度学习设计AI麻将程序
|
存储 算法 Python
秒懂算法 | 子集树模型——0-1背包问题的回溯算法及动态规划改进
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为W。一种物品要么全部装入背包,要么全部不装入背包,不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品,使得装入背包中的物品总价值最大?
818 0
秒懂算法 | 子集树模型——0-1背包问题的回溯算法及动态规划改进
【数据结构之树】——什么是树,树的特点,树的相关概念和表示方法以及在实际的应用。
一、1.树是什么? 树是一种非线性的数据结构,它是由n(n&gt;=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。