数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学C++ 中的不同岛屿数量
假设我们有一个二进制二维数组网格，这里一个岛屿是一组 1（陆地），通过 4 个方向（水平或垂直）连接。我们可以假设网格的所有四个边缘都被水包围。我们必须计算不同岛屿的数量。
当一个岛屿可以通过平移（而不是旋转或反射）等于另一个岛屿时，则认为该岛屿与另一个岛屿相同。
因此，如果输入类似于
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
那么输出将为 3
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 dfs()，它将接收 x、y、grid、temp、c 作为参数。
如果 x 和 y 不在网格的行和列内部，并且 grid[x,y] 为 0，则：
返回
grid[x, y] := 0
temp := temp 连接 c
dfs(x + 1, y, grid, temp, 'r')
dfs(x - 1, y, grid, temp, 'l')
dfs(x, y + 1, grid, temp, 'd')
dfs(x, y - 1, grid, temp, 'u')
temp := temp 连接 'b'
从主方法执行以下操作：
ret := 0
定义一个集合 visited
对于初始化 i := 0，当 i < 网格的行数时，更新（i 增加 1），执行：
对于初始化 j := 0，当 j < 网格的列数时，更新（j 增加 1），执行：
如果 grid[i, j] 不为零，则：
aux := 空字符串
dfs(i, j, grid, aux, 's')
如果 aux 不在 visited 中，则：
(ret 增加 1)
将 aux 插入 visited
返回 ret
示例
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
void dfs(int x, int y, vector < vector <int> >& grid, string& temp, char c){
if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || !grid[x][y])
return;
grid[x][y] = 0;
temp += c;
dfs(x + 1, y, grid, temp, 'r');
dfs(x - 1, y, grid, temp, 'l');
dfs(x, y + 1, grid, temp, 'd');
dfs(x, y - 1, grid, temp, 'u');
temp += 'b';
}
int numDistinctIslands(vector<vector<int>>& grid) {
int ret = 0;
set<string> visited;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j]) {
string aux = "";
dfs(i, j, grid, aux, 's');
if (!visited.count(aux)) {
ret++;
visited.insert(aux);
}
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v =
{{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}};
cout<<(ob.numDistinctIslands(v));
}输入
{{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}}输出
3
更新于：2020-11-17
212 次查看
广告