通吃岛屿问题
通吃岛屿问题
总结：本节使用bfs与dfs通吃岛屿问题，后面还会有更多类似文章，期待留言交流！
1.岛屿问题
在秋招及实习期间发现岛屿问题在面试中会被经常问到，本节来把leetcode上的所有岛屿问题通吃一遍。
本节涉及的题目依次如下：
- 200.岛屿数量
https://leetcode-cn.com/problems/number-of-islands/
- 694.不同岛屿的个数
https://leetcode-cn.com/problems/number-of-distinct-islands/
- 711.不同岛屿的个数II
https://leetcode-cn.com/problems/number-of-distinct-islands-II/
- 695.岛屿的最大面积
https://leetcode-cn.com/problems/max-area-of-island/
- 463.岛屿的周长
https://leetcode-cn.com/problems/island-perimeter/
2.逻辑汇总
针对以上题目，先分析不同题目的区别，随后给出相应的模板的解决这种问题，拿最简单的第200题来说。
第200题目如下：
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
解法描述：针对这种问题我们可以采用dfs/bfs来解决，当然也可以才uf算法来解决，本节我们主要来套用dfs/bfs。
dfs算法与bfs算法不懂的就不多阐述了，本节的所有知识体系是建立在你知道该算法的基础之上，进行最佳实践。
下面给出一个bfs框架：
class Solution {
private:
int direct[4][2] = {
{0, 1},
{0, -1},
{1, 0},
{-1, 0}};
vector<vector<bool>> visited;
int n, m;
public:
// bfs
int numIslands(vector<vector<char>> &grid)
{
n = grid.size();
if (n == 0)
{
return 0;
}
m = grid[0].size();
visited = vector<vector<bool>>(n, vector<bool>(m, false));
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == '1' && !visited[i][j]) // 是小岛
{
visited[i][j] = true;
// bfs逻辑
ans++; // 岛屿数量
}
}
}
return ans;
}
bool inArea(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y < m;
}
};
相信上面代码一看就会，值得说明的一点使用了visit来判断是否再次访问，用来标记已经访问过的点。
下来就是bfs的主要逻辑，无非就是一个队列，然后进出队列即可，明确以下几点：
- 何时出队列
- 何时进队列
出队列没啥好说的，只有进去的出就完事了，进队列那就是满足特定条件，这里特定条件有：
- 新节点(上下左右四个方向的节点)未访问过
- 新节点是岛
- 新节点未超出边界
接下来就是中间bfs的逻辑：
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int newX = x + direct[k][0];
int newY = y + direct[k][1];
if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == '1')
{
q.push({newX, newY});
visited[newX][newY] = true;
}
}
}
简单吧~
随后，给大家一个dfs框架，bfs外壳不变，改掉内部的bfs部分即可。
与dfs框架不同在于两点：
visited[i][j] = truedfs内部处理- bfs逻辑替换未dfs逻辑
// 其他部分不变
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == '1' && !visited[i][j])
{
int area = dfs(grid, i, j); // 这里变了
ans++;
}
}
}
// 其他部分不变
dfs逻辑我们要明白，什么时候递归终止，如何防止死递归。
- 防止死递归，前面有个visited即可防止
- 递归终止：新节点不在网格区域或者在网格区域但是被访问过，再或者不是岛。
int dfs(vector<vector<char>> &grid, int x, int y)
{
if (!inArea(x, y) || (inArea(x, y) && visited[x][y]) || grid[x][y] == '0')
return 0;
int area = 1; // (x,y)
visited[x][y] = true;
for (int i = 0; i < 4; i++)
{
int newX = x + direct[i][0];
int newY = y + direct[i][1];
area += dfs(grid, newX, newY);
}
return area;
}
上述两个代码完整版：
- bfs
class Solution
{
private:
int direct[4][2] = {
{0, 1},
{0, -1},
{1, 0},
{-1, 0}};
vector<vector<bool>> visited;
int n, m;
public:
// bfs
int numIslands(vector<vector<char>> &grid)
{
n = grid.size();
if (n == 0)
{
return 0;
}
m = grid[0].size();
visited = vector<vector<bool>>(n, vector<bool>(m, false));
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == '1' && !visited[i][j])
{
visited[i][j] = true;
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int newX = x + direct[k][0];
int newY = y + direct[k][1];
if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == '1')
{
q.push({newX, newY});
visited[newX][newY] = true;
}
}
}
ans++;
}
}
}
return ans;
}
bool inArea(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y < m;
}
};
- dfs
class Solution
{
private:
int direct[4][2] = {
{0, 1},
{0, -1},
{1, 0},
{-1, 0}};
vector<vector<bool>> visited;
int n, m;
public:
int numIslands(vector<vector<char>> &grid)
{
n = grid.size();
if (n == 0)
{
return 0;
}
m = grid[0].size();
visited = vector<vector<bool>>(n, vector<bool>(m, false));
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == '1' && !visited[i][j])
{
int area = dfs(grid, i, j);
ans++;
}
}
}
return ans;
}
int dfs(vector<vector<char>> &grid, int x, int y)
{
if (!inArea(x, y) || (inArea(x, y) && visited[x][y]) || grid[x][y] == '0')
return 0;
int area = 1; // (x,y)
visited[x][y] = true;
for (int i = 0; i < 4; i++)
{
int newX = x + direct[i][0];
int newY = y + direct[i][1];
area += dfs(grid, newX, newY);
}
return area;
}
bool inArea(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y < m;
}
};
好了，明白上述bfs与dfs操作，我们可以分分钟感到665.岛屿的最大面积与463.岛屿的周长。
695.岛屿的最大面积
这道题是上面那道题的变种，上面是求有多少个岛屿，这道题是所有岛屿面积中最大的，那简单啊，直接统计面积，取max就行了，这也是为什么上面那道题dfs算法框架我返回值是int，并且里面我也计算了area，bfs框架中添加下面三行即可，其他不变。
if (grid[i][j] == 1 && !visited[i][j])
{
// todo
int area = 1; // this line
while (!q.empty())
{
// todo
for (int k = 0; k < 4; k++)
{
// todo
if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1)
{
area++; // this line
}
}
}
ans = max(ans, area); // this line
}
dfs代码改的更少：只需要更改this line即可。
if (grid[i][j] == 1 && !visited[i][j])
{
int area = dfs(grid, i, j);
ans = max(ans, area); // this line
}
463.岛屿的周长
这道题有点意思，围绕的周长，其实可以两句话概括：
- 岛屿变水域或边界 加1
- 水域之间不变
bfs实现：只需要修改下面几行即可。
if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1)
{
q.push({newX, newY});
visited[newX][newY] = true;
}
else if (!inArea(newX, newY) || grid[newX][newY] == 0) // this line
{
ans++;
}
dfs实现：切记area有1变为0，因为前面计算的是面积，1代表的是当前节点，而这里改为0是因为我们计算周长，原理都不一样，一定要好好体会。
除此之外修改之前的终止条件未下面两行即可。
- 岛屿变水域或边界 加1
返回1表示超出边界或者进入水域。
int dfs(vector<vector<int>> &grid, int x, int y)
{
// 岛屿变水域或边界 加1
if (!inArea(x, y) || grid[x][y] == 0) return 1;
if (inArea(x, y) && visited[x][y]) return 0;
// 水域之间不变
int area = 0;
// 其余不变
}
最后，就是两个比较麻烦的题目。
694.不同岛屿的个数
11
1
1
11
这两个表示不同的岛屿。
711.不同岛屿的个数II
11
1
1
11
这两个表示相同的岛屿。
711是694的提升版，进行旋转、对称之后的岛屿是一样的，那么就是相同岛屿，而694只认为平移相同才算相同的岛屿。
先看694题解法。我们重点就是判重就行了，需要使用一种方式来表达不同岛屿。这里采用坐标相对偏移来保证这一点。
例如：
11
1
假设我们遍历方式是bfs，并且先下后右，那么依次的偏移：
[[0,0],[1,0],[0,1]]
同理，得到
1
11
为：
[[0,0],[1,0],[1,1]]
那么它们只要形状不同，必定这个结果是不同的，我们可以采用两种形式刻画相对偏移：
- 比较数组结构
[[0,0],[1,0],[0,1]]是否等于[[0,0],[1,0],[1,1]]
- 比较字符串结构
0_0_1_0_0_1_是否等于0_0_1_0_1_1_
可以明显发现第二种方法是比较优的。
是否等于我们可以用一个set刻画，这样只要往里面插入永远是不一样的，最后返回set的大小就是不同岛屿个数，接下来我们按照这两种方式来进行阐述。
- 数组结构的bfs
visited[i][j] = true;
queue<pair<int, int>> q;
q.push({i, j});
vector<pair<int, int>> axis; // this line 没有放入[0,0]坐标
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int newX = x + direct[k][0];
int newY = y + direct[k][1];
if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1)
{
q.push({newX, newY});
visited[newX][newY] = true;
axis.push_back({newX - i, newY - j}); // this line
}
}
}
s.insert(axis); // this line
只需要改动最上面框架的三行就可以实现。
- 数组结构的dfs
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == 1 && !visited[i][j])
{
vector<pair<int, int>> axis; // this line
dfs(grid, i, j, axis); // this line
s.insert(axis); // this line
}
}
}
dfs中修改：
void dfs(vector<vector<int>> &grid, int x, int y, vector<pair<int, int>>& axis) {
if (!inArea(x, y) || (inArea(x, y) && visited[x][y]) || grid[x][y] == 0) {
return;
}
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + direct[i][0];
int newY = y + direct[i][1];
axis.push_back({newX-x,newY-y}); // this line
dfs(grid, newX, newY, axis);
}
}
可以看到标记this line的贼少。
- 字符串结构的bfs与dfs
同理，把上述的axis.push_back({newX-x,newY-y});改为下面一行就可以实现字符串结构的bfs。
encode += to_string(newX - i) + "_" + to_string(newY - j) + "_";
接下来，我们来看一下，最后一道题711，711是在694的基础上进行演化，允许旋转、对称作为一样的图行，我们只需要写一个正规化函数，得到岛屿的坐标数组后，进行正规化处理，放入set即可。
关键点便是正规化函数如何实现：
我们知道：一个点[x,y]对称可以得到[x,-y],[-x,y],[-x,-y]，交换x与y，得到：[y,x],[y,-x],[-y,x],[-y,-x]。
因此我们得到一个结论：得到一个岛屿对应的数组，该数组可以找到8种结构(包含自身)。
为了统一，由于顺序不同引起，还会有多种结果，所以我们需要通过排序，这样每次一个岛屿的形状(旋转、对称)正规化后得到的一个正规化结果一定是一样的。
bfs实现：
set<vector<pair<int, int>>> s;
visited = vector<vector<bool>>(n, vector<bool>(m, false));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == 1 && !visited[i][j])
{
visited[i][j] = true;
queue<pair<int, int>> q;
q.push({i, j});
vector<pair<int, int>> axis{{i,j}};
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int newX = x + direct[k][0];
int newY = y + direct[k][1];
if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1)
{
q.push({newX, newY});
visited[newX][newY] = true;
axis.push_back({newX,newY}); // this line
}
}
}
s.insert(Normalize(axis)); // this line
}
}
}
dfs实现：
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
vector<pair<int, int>> axis;
dfs(grid, i, j, axis);
s.insert(Normalize(axis)); // this line
}
}
}
void dfs(vector<vector<int>> &grid, int x, int y, vector<pair<int, int>>& axis) {
if (!inArea(x, y) || (inArea(x, y) && visited[x][y]) || grid[x][y] == 0) {
return;
}
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + direct[i][0];
int newY = y + direct[i][1];
axis.push_back({newX,newY}); // this line
dfs(grid, newX, newY, axis);
}
}
结构写好了，我们来写正规化函数：
所有想说的都在前面提到了，配上注释看。
vector<pair<int,int>> Normalize(const vector<pair<int,int>>& rawShape) {
vector<vector<pair<int,int>>> shapes(8); // 旋转+镜像
// 得到每一种形状
for (auto& sp : rawShape) {
int x = sp.first;
int y = sp.second;
// 镜像
shapes[0].push_back({x,y});
shapes[1].push_back({x,-y});
shapes[2].push_back({-x,y});
shapes[3].push_back({-x,-y});
// 旋转
shapes[4].push_back({y, x});
shapes[5].push_back({y,-x});
shapes[6].push_back({-y,x});
shapes[7].push_back({-y,-x});
}
for (auto& sp : shapes) {
// 每种shape进行排序
sort(sp.begin(), sp.end());
// 得到这种shape的相对坐标
for (int i=rawShape.size()-1;i>=0;i--) {
sp[i].first -= sp[0].first;
sp[i].second -= sp[0].second;
}
}
// 所有相对坐标的不同shape进行排序
sort(shapes.begin(), shapes.end());
return shapes[0]; // 随便取一种
}
总结：本节使用bfs与dfs通吃岛屿问题，后面还会有更多类似文章，期待留言交流！