LEETCODE 1254 统计封闭岛屿的数目 Number of Closed Islands
地址 https://leetcode-cn.com/contest/weekly-contest-162/problems/number-of-closed-islands/
有一个二维矩阵 grid
,每个位置要么是陆地(记号为 0
)要么是水域(记号为 1
)。
我们从一块陆地出发,每次可以往上下左右 4 个方向相邻区域走,能走到的所有陆地区域,我们将其称为一座「岛屿」。
如果一座岛屿 完全 由水域包围,即陆地边缘上下左右所有相邻区域都是水域,那么我们将其称为 「封闭岛屿」。
请返回封闭岛屿的数目。
示例1
输入:grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出:2
解释:
灰色区域的岛屿是封闭岛屿,因为这座岛屿完全被水域包围(即被 1 区域包围)。
示例2
输入:grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出:1
示例3
输入:grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
输出:2
题解 基本都是使用DFS 查找是否与边界的0有所连通
这里提供另一种思路 并查集
检测所有标记为陆地的0 进行归并 然后将与边界连通的陆地集合删除 最后留下的就是封闭岛屿
代码
class Solution {
public: int MAX_NUM;
vector<vector<int>> field;
vector<int> fa;
vector<int> addx;
vector<int> addy;
void init(int n)
{
for (int i = ; i <= n; i++)
fa[i] = i;
}
int get(int x)
{
return fa[x] == x ? x : fa[x] = get(fa[x]);//路径压缩,防止链式结构
}
void merge(int x, int y)
{
fa[get(x)] = get(y);
}
//================================================
void check(int x, int y, vector<vector<int>>& grid)
{
for (int i = ; i < ; i++) {
int newx = x + addx[i];
int newy = y + addy[i]; if (newx >= && newx < grid.size() && newy >= && newy < grid[].size()
&& grid[newx][newy] == )
{
int idx = x * grid[].size() + y;
int anotherIdx = newx * grid[].size() + newy;
merge(idx, anotherIdx);
}
}
} int closedIsland(vector<vector<int>>& grid) {
MAX_NUM = ;
field = vector<vector<int>>(MAX_NUM, vector<int>(MAX_NUM));
fa = vector<int>(MAX_NUM*MAX_NUM + );
init(MAX_NUM*MAX_NUM);
addx = vector<int>{ ,-,, };
addy = vector<int>{ ,,-, };
for (int i = ; i < grid.size(); i++) {
for (int j = ; j < grid[].size(); j++) {
if (grid[i][j] == ) {
check(i, j, grid);
}
}
} set<int> s; for (int i = ; i < grid.size(); i++) {
for (int j = ; j < grid[].size(); j++) {
if (grid[i][j] == ) {
int idx = i * grid[].size() + j;
s.insert(get(idx));
}
}
} //从统计的并查集 删除与边沿有关的陆地
for (int i = ; i < grid.size(); i++) {
for (int j = ; j < grid[].size(); j++) {
if (grid[i][j] == && (i == || i == grid.size() - || j == || j == grid[].size() - )) {
int idx = i * grid[].size() + j;
s.erase(get(idx));
}
}
} return s.size();
} };
最新文章
- bzoj1191--匈牙利算法
- Secure Digital
- JS的循环、复杂运算符
- xscript脚本
- UWP开发入门系列笔记之(一):UWP初览
- HDU-1584 蜘蛛牌(dfs)
- 专注VR/AR广告 ,内容感知广告公司Uru获80万美元投资
- (5)Maven快速入门_5maven聚合与继承_scope依赖范围
- FFT算法详解
- 第27月第10天 cmake
- springboot打包部署到tomcat
- Docker 系列01: Centos7.3 上安装docker
- PostgreSQL10.5安装详细步骤(Win10)
- github for windows 使用
- SpringMVC 实现返回一段数据 &; 实现自动发送json格式数据 - AJAX
- 深度学习材料:从感知机到深度网络A Deep Learning Tutorial: From Perceptrons to Deep Networks
- leetcode-852-山脉数组的峰顶索引
- orcal 数据库 maven架构 ssh框架 的全xml环境模版 及常见异常解决
- Spring整合JUnit4进行AOP单元测试的时候,报:";C:\Program Files\Java\jdk1.8.0_191\bin\java.exe"; -ea -Didea.test.cyclic.buffer.size=1048576 ";-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2018.3\lib\idea_rt.jar=64
- codeforces741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths