首页 > 试题广场 >

几个岛

[编程题]几个岛
  • 热度指数：4023 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给定一个m行n列的二维地图, 初始化每个单元都是水.
操作addLand 把单元格(row,col)变成陆地.
岛屿定义为一系列相连的被水单元包围的陆地单元, 横向或纵向相邻的陆地称为相连(斜对角不算).
在一系列addLand的操作过程中, 给出每次addLand操作后岛屿的个数.
二维地图的每条边界外侧假定都是水.

输入描述:
多组测试数据，请参考例题处理 每组数据k+3行, k表示addLand操作次数 第一行:表示行数m 第二行:表示列数n 第三行:表示addLand操作次数k 第4~k+3行:row col 表示addLand的坐标。注意超过边界的坐标是无效的。


输出描述:
一行,k个整数, 表示每次addLand操作后岛屿的个数, 用空格隔开，结尾无空格
示例1

输入

3
3
4
0 0
0 1
1 2
2 1

输出

1 1 2 3
算法知识视频讲解
开通博客
头像 bandiaoz
发表于 2024-12-26 17:44:32
解题思路 这是一道动态岛屿统计问题，主要思路如下： 问题分析： 给定m×n的二维地图，初始全是水 每次addLand操作会将一个格子变成陆地 相邻的陆地（上下左右）形成一个岛屿 需要统计每次操作后的岛屿数量 解决方案： 使用vector存储每个岛屿的点集 每次添加新点时检查是否能与现有 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 实习_机器学习_广东或四川_5月中可入职
发表于 2025-03-16 22:58:02
import re import copy m,n,k = [int(input()) for _ in range(3)] grid = [[0]*n for _ in range(m)] res = [] if n == 0 or m == 0: print(0) def dfs(gr 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 测试工程师 图 PHP工程师 滴滴 自动驾驶/地图融合 系统工程师 模拟 测试开发工程师 2018 Java工程师
上传者：小小
难度：
31条回答 12874浏览

热门推荐

通过挑战的用户

查看代码

相关试题

几个岛

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号