菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
144
0

C++9018:1152——细胞问题

原创
05/13 14:22
阅读数 82838

题目来自:http://218.5.5.242:9018/JudgeOnline/problem.php?id=1152

     http://ybt.ssoier.cn:8088/problem_show.php?pid=1329

     https://www.luogu.com.cn/problem/P1451

题目描述

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

如:阵列

0234500067
1034560500
2045600671
0000000089  
有4个细胞


输入

第一行 :两个数字M N (1<=M<=50 1<=N<80)表示该阵列有M行N列,从第2行到第M+1行 每行有连续的N个字符。

输出

一行: 细胞个数。

样例输入

4 10
0234500067
1034560500
2045600671
0000000089

样例输出

4

作者分析:这道题是一道经典的DFS搜索的题目,使用DFS求连通块,注意,洛谷的题目需改变数组的大小。
#include <iostream>
#include <cstring>
using namespace std;

int idx[51][81],m,n,ans = 0;
char a[51][81];

void dfs(int x,int y,int id){
    if (x < 0 || x >= m || y < 0 || y >= n) return;
    if (idx[x][y] > 0 || a[x][y] == '0') return;
    idx[x][y] = id;
   // 上下左右搜索 dfs(x
- 1,y,id); dfs(x + 1,y,id); dfs(x,y + 1,id); dfs(x,y - 1,id); } int main(){ memset(a,0,sizeof(a)); memset(idx,0,sizeof(idx)); cin >> m >> n; for (int i = 0;i < m;i++){ cin >> a[i]; } int cnt = 0; for (int i = 0;i < m;i++){ for (int j = 0;j < n;j++){ if (idx[i][j] == 0 && a[i][j] != '0'){ dfs(i,j,++cnt); } } } cout << cnt; return 0; }
 

发表评论

0/200
144 点赞
0 评论
收藏