岛屿问题
1.岛屿类题目的本质是二维数组的遍历问题, 把二维数组可以看成是一种特殊的图, 遍历的时候有上下左右四个方向, 通常采用dfs进行遍历
2.遍历过程中首先维护一个方向数组
vector<vector<int>> dirs = {{-1,0}, {0,-1}, {1,0}, {0,1}}
表示可以变化的四个方向
3.遍历的时候首先判断是否越界, 然后判断是否已经遍历过, 因此用另一个 visited[i][j] 标记是否已经遍历过
4.遍历只需要去 dfs 邻居四个方向节点
5.岛屿题的主要框架为
// 方向数组
vector<vector<int>> dirs = {{-1,0}, {0,-1}, {1,0}, {0,1}};
void dfs(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& visited) {
int m = grid.size();
int n = grid[0].size();
if (i < 0 || j < 0 || i >= m || j >= n) {
return;
}
if (visited[i][j]) {
return;
}
visited[i][j] = true;
for (vecotr<int>& d : dirs) {
int neighborX = i + d[0];
int neighborY = j + d[1];
dfs(neighborX, neighborY, grid, visited);
}
return;
}
200.岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。示例 1：
输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1示例 2：
输入：grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出：3
分析:
1.dfs 岛屿经典题目, 针对所有的位置进行遍历, 遍历到当前节点的时候, 岛屿数量+=1, dfs 它的四个方向, 如果还是岛屿那么标记成海洋避免重复计算
class Solution {
private:
int ans = 0;
public:
const vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void dfs(vector<vector<char>>& grid, int i, int j) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) {
return;
}
if (grid[i][j] == '0') {
return;
}
if (grid[i][j] == '1') {
grid[i][j] = '0';
for (int k = 0; k < 4; ++k) {
int nx = i + dirs[k][0];
int ny = j + dirs[k][1];
dfs(grid, nx, ny);
}
}
return;
}
int numIslands(vector<vector<char>>& grid) {
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
++ans;
dfs(grid, i, j);
}
}
}
return ans;
}
};
1254.统计封闭岛屿的数目
二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。示例 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
分析:
1.题目中只统计封闭的岛屿, 也就是说需要把和四周相连的岛屿用水覆盖掉, 剩下的遍历并且 dfs 合并得到的岛屿就是封闭的岛屿了
class Solution {
private:
int m;
int n;
int count = 0;
const vector<vector<int>> dirs = {{-1,0}, {0,-1}, {1,0}, {0,1}};
public:
void dfs(int i, int j, vector<vector<int>>& grid) {
if (i < 0 || j < 0 || i >= m || j >= n)
return;
if (grid[i][j] == 1)
return;
grid[i][j] = 1;
for (int k = 0; k < 4; ++k) {
int neighborX = i + dirs[k][0];
int neighborY = j + dirs[k][1];
dfs(neighborX, neighborY, grid);
}
return;
}
int closedIsland(vector<vector<int>>& grid) {
m = grid.size();
if (m == 0)
return count;
n = grid[0].size();
for (int i = 0; i < m; ++i) {
dfs(i, 0, grid);
dfs(i, n-1, grid);
}
for (int j = 0; j < n; ++j) {
dfs(0, j, grid);
dfs(m-1, j, grid);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) {
++count;
dfs(i, j, grid);
}
}
}
return count;
}
};
1020.飞地的数量
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。示例 1：输入：grid = [
[0,0,0,0],
[1,0,1,0],
[0,1,1,0],
[0,0,0,0]
]
输出：3 解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。示例 2：输入：grid = [
[0,1,1,0],
[0,0,1,0],
[0,0,1,0],
[0,0,0,0]
]
输出：0 解释：所有 1 都在边界上或可以到达边界。
分析:
1.封闭岛屿的加法求和翻版, 但要对封闭的区块求和, 求出封闭区域之后, 多加一步对结果进行求和
class Solution {
public:
int m;
int n;
int count = 0;
const vector<vector<int>> dirs = {{-1,0}, {0,-1}, {1,0}, {0,1}};
void dfs(int i, int j, vector<vector<int>>& grid) {
if (i < 0 || j < 0 || i >= m || j >= n)
return;
if (grid[i][j] == 0)
return;
grid[i][j] = 0;
for (int k = 0; k < 4; ++k) {
int neighborX = i + dirs[k][0];
int neighborY = j + dirs[k][1];
dfs(neighborX, neighborY, grid);
}
return;
}
int numEnclaves(vector<vector<int>>& grid) {
m = grid.size();
if (m == 0)
return count;
n = grid[0].size();
for (int i = 0; i < m; ++i) {
dfs(i, 0, grid);
dfs(i, n-1, grid);
}
for (int j = 0; j < n; ++j) {
dfs(0, j, grid);
dfs(m-1, j, grid);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++count;
}
}
}
return count;
}
};
695.岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。示例 1：
输入：grid = [
[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]
]
输出：6 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。示例 2：输入：grid = [[0,0,0,0,0,0,0,0]] 输出：0
分析:
1.需要返回最大岛屿的面积, 因此遍历所有的位置, dfs需要返回从当前节点出发的面积
class Solution {
private:
int maxArea = 0;
int m;
int n;
public:
int dfs(int i, int j, vector<vector<int>>& grid) {
if (i < 0 || j < 0 || i >= m || j >= n) {
return 0;
}
if (grid[i][j] == 0) {
return 0;
}
grid[i][j] = 0;
return 1 + dfs(i+1, j, grid) + dfs(i, j+1, grid) + dfs(i-1, j, grid) + dfs(i, j-1, grid);
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size();
if (m == 0)
return 0;
n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
maxArea = max(maxArea, dfs(i, j, grid));
}
}
}
return maxArea;
}
};
1905.统计子岛屿
给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。请你返回 grid2 中 子岛屿 的 数目 。
示例 1：输出：3 解释：如上图所示，左边为 grid1 ，右边为 grid2 。grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。
示例 2：输入：grid1 = [
[1,0,1,0,1],
[1,1,1,1,1],
[0,0,0,0,0],
[1,1,1,1,1],
[1,0,1,0,1]
],
grid2 = [
[0,0,0,0,0],
[1,1,1,1,1],
[0,1,0,1,0],
[0,1,0,1,0],
[1,0,0,0,1]
]
输出：2 解释：如上图所示，左边为 grid1 ，右边为 grid2 。grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。
分析:
1.子岛屿的判断条件: grid2 中的岛屿完全存在 grid1 中某个岛屿中; 否明命题是grid2中的某一块陆地 grid[i][i] 在 grid1 中是海洋, 那么就不是子岛屿
2.这里一种判断方法是, 先排除所有的不可能是子岛屿的岛屿, 然后用水淹掉, 剩下的岛屿那么就是子岛屿了
class Solution {
private:
int m;
int n;
int cnt = 0;
public:
void dfs(int i, int j, vector<vector<int>>& grid2) {
if (i < 0 || j < 0 || i >= m || j >= n)
return;
if (grid2[i][j] == 0)
return;
grid2[i][j] = 0;
dfs(i+1, j, grid2);
dfs(i-1, j, grid2);
dfs(i, j+1, grid2);
dfs(i, j-1, grid2);
return;
}
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
m = grid2.size();
if (m == 0)
return cnt;
n = grid2[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j] == 1 && grid1[i][j] == 0) {
dfs(i, j, grid2);
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j] == 1) {
++cnt;
dfs(i, j, grid2);
}
}
}
return cnt;
}
};
694.不同岛屿的数量
给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。
请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。示例 1：输入: grid = [
[1,1,0,0,0],
[1,1,0,0,0],
[0,0,0,1,1],
[0,0,0,1,1]
]
输出：1示例 2：输入: grid = [
[1,1,0,1,1],
[1,0,0,0,0],
[0,0,0,0,1],
[1,1,0,1,1]
] 输出: 3
分析:
1.这道题需要找到形状不同的岛屿的数量, 相同仅仅定义为平移相同, 不包括翻转和旋转相同; 需要编码遍历的路径, 也就是说对遍历路径编码成唯一的字符串
2.首先对于相同形状的岛屿, 如果从统一起点出发, dfs 遍历的顺序是一样的
void dfs(int i, int j, vector<vector<int>>& grid2) {
dfs(i-1, j, grid2); // 下
dfs(i+1, j, grid2); // 上
dfs(i, j-1, grid2); // 右
dfs(i, j+1, grid2); // 右
return;
}
3.对于以下的岛屿, 遍历顺序如果下, 右, 上, 撤销上(下), 撤销右(左), 撤销下(上)
11
11
得到的序列是唯一的2,4,1,-1,-4,-2
4.为啥非得用撤销这种操作呢? 比如我们遍历如下结果
1
11
可以用[下, 右]不行吗? 不行, 用撤销是为了区分两种可能的遍历顺序, 例如[下, 右, 撤销下, 撤销右]和[下, 撤销下, 右, 撤销右]
5.所以我们遍历的时候增加个方向, 用1,2,3,4分别表示上下左右, 用-1,-2,-3,-4表示撤销对应的上下左右, 就可以唯一化编码路径
class Solution {
public:
int m;
int n;
void dfs(int i, int j, string& s, int dir, vector<vector<int>>& grid) {
if (i < 0 || j < 0 || i >= m || j >= n)
return;
if (grid[i][j] == 0)
return;
// 前序遍历位置
grid[i][j] = 0;
s += ",";
dfs(i-1, j, s, 1, grid); // 下
dfs(i+1, j, s, 2, grid); // 上
dfs(i, j-1, s, 3, grid); // 右
dfs(i, j+1, s, 4, grid); // 右
// 后序遍历位置: 进行一个回溯操作
s += to_string(-dir);
s += ",";
return;
}
int numDistinctIslands(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
unordered_set<string> hash;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
string s = "";
dfs(i, j, s, 0, grid);
hash.insert(s);
}
}
}
return hash.size();
}
};
711.不同岛屿的数量 II
给定一个 m x n 二进制数组表示的网格 grid ，一个岛屿由 四连通 （上、下、左、右四个方向）的 1 组成（代表陆地）。你可以认为网格的四周被海水包围。
如果两个岛屿的形状相同，或者通过旋转（顺时针旋转 90°，180°，270°）、翻转（左右翻转、上下翻转）后形状相同，那么就认为这两个岛屿是相同的。
返回 这个网格中形状 不同 的岛屿的数量 。示例 1: 输入: grid = [
[1,1,0,0,0],
[1,0,0,0,0],
[0,0,0,0,1],
[0,0,0,1,1]
] 输出: 1
解释: 这两个是相同的岛屿。因为我们通过 180° 旋转第一个岛屿，两个岛屿的形状相同。示例 2: 输入: grid = [
[1,1,0,0,0],
[1,1,0,0,0],
[0,0,0,1,1],
[0,0,0,1,1]
] 输出: 1
分析:
1.这道题比上一道题复杂, 在于说如果是完全平移变化, 只用遍历的顺序可以实现序列化编码, 但是这道题带了旋转, 就需要进行唯一形状编码. 如何编码唯一化的图形? 有两种常见的做法, 一种只是利用旋转翻转平移的几何关系进行编码, 另一种是利用欧式距离取哈希编码
2.可以将岛屿的每块陆地坐标 (x,y) 都看做是向量, 然后利用解析几何只是计算出每个向量变换后的结果, 依次是 (以下旋转操作默认为顺时针旋转)
对坐标 (x,y)
顺时针旋转90度/180度/270度分别得到(y,-x) (-x,y) (-x,-y)
左右翻转(-x,y)
上下翻转(x,-y)
还有两种比较复杂的翻转
旋转90度且左右翻转(y,x) 等价于旋转270度且上下翻转
旋转270度且左右翻转(-y,-x) 等价于旋转90度且上下翻转
因此, 以上集中复杂的方式可以合并为8种可能性, 对于每一种旋转得到的结果, 需要先算出每个点的归一化的坐标值, 也就是是说以原点为(0, 0)的坐标值 归一化坐标值的方法是: 对于每一个坐标点, 先找到8个(剩余7个)旋转点, 然后分别计算出这8个点的横坐标最小值和纵坐标的最小值, 然后用8个坐标点都去减去这个最小值, 得到归一化坐标点之后 对每个坐标进行dfs, 并找到8个点进行规范化canocialize, 规范化的操作: 比如把8个生成的坐标点放在vector
3.上面的方法实现还是比较复杂的, 这里hash: 对于岛屿上的所有点, 可以用两两坐标之间的欧式距离和进行哈希
分析:
1.按照解析几何关系编码的方法写的时间很长, 能用欧式距离编码就用欧式距离编码, 代码不容易出错
2.对任意岛屿坐标集合, hash = sum(两两坐标点欧式距离)
class Solution {
public:
int m;
int n;
int count = 0;
vector<double> distanceSumHash;
vector<pair<int, int>> coordinates;
const double eps = 1e-10;
void dfs(int i, int j, vector<vector<int>>& grid) {
if (i < 0 || j < 0 || i >= m || j >= n)
return;
if (grid[i][j] == 0)
return;
grid[i][j] = 0;
coordinates.push_back({i, j});
dfs(i+1, j, grid);
dfs(i, j+1, grid);
dfs(i-1, j, grid);
dfs(i, j-1, grid);
return;
}
double calcuSumDistanceHash() {
double sum = 0;
for (int i = 0; i < coordinates.size(); ++i) {
for (int j = i+1; j < coordinates.size(); ++j) {
double dist = 0;
int x1 = coordinates[i].first;
int y1 = coordinates[i].second;
int x2 = coordinates[j].first;
int y2 = coordinates[j].second;
int dx = x1 - x2;
int dy = y1 - y2;
sum += sqrt(dx * dx + dy * dy);
}
}
return sum;
}
bool checkConflict(double curHash) {
bool ifConflict = false;
for (double d : distanceSumHash) {
if (abs(d - curHash) < eps) {
ifConflict = true;
break;
}
}
return ifConflict;
}
int numDistinctIslands2(vector<vector<int>>& grid) {
m = grid.size();
if (m == 0)
return count;
n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
coordinates.clear();
dfs(i, j, grid);
double hashValue = calcuSumDistanceHash();
if (!checkConflict(hashValue)) {
distanceSumHash.push_back(hashValue);
}
}
}
}
return distanceSumHash.size();
}
};
转载请注明来源, from goldandrabbit.github.io
