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 Java 数据库连接
Hive教程(08)- JDBC操作Hive
Hive教程(08)- JDBC操作Hive
331 0
|
9月前
|
前端开发 Python
如何用Python快速搭建一个文件传输服务
如何用Python快速搭建一个文件传输服务
|
11月前
1358:中缀表达式值(expr)
1358:中缀表达式值(expr)
107 0
|
数据可视化 前端开发 JavaScript
pyEcharts安装及详细使用指南(一)
pyEcharts安装及详细使用指南(一)
1331 0
pyEcharts安装及详细使用指南(一)
|
11月前
1360:奇怪的电梯(lift)
1360:奇怪的电梯(lift)
|
11月前
1270:【例9.14】混合背包
1270:【例9.14】混合背包
|
11月前
1355:字符串匹配问题(strs)
1355:字符串匹配问题(strs)
|
11月前
|
人工智能
天梯赛-L1-064 估值一亿的AI核心代码 (20 分)--2019全国CCCC天梯赛L1题解
天梯赛-L1-064 估值一亿的AI核心代码 (20 分)--2019全国CCCC天梯赛L1题解
319 0
|
11月前
1336:【例3-1】找树根和孩子
1336:【例3-1】找树根和孩子
|
8月前
|
测试技术
针对三角形问题,使用边界值分析法设计测试用例
一、测试问题描述 输入三个整数a、b、c,分别作为三角形的三条边,通过程序判断这三条边是否能构成三角形?如果能构成三角形,则判断三角形的类型(等边三角形、等腰三角形、一般三角形)。要求输入三个整数a、b、c,必须满足以下条件:1≤a≤200;1≤b≤200
425 0

热门文章

最新文章