数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的不同岛屿 II 的数量
假设我们有一个非空的二维二进制数组，称为 grid，这里一个岛屿是由 4 个方向连接的 1（表示陆地）组成的群组。我们还可以假设网格的所有四个边缘都环绕着水。
我们必须计算不同岛屿的数量。如果两个岛屿具有相同的形状，或者在仅旋转 90、180 或 270 度或左右方向或上下方向反射后具有相同的形状，则认为它们是相同的。
因此，如果输入类似于：
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
则输出将为 1
为了解决这个问题，我们将遵循以下步骤：
定义一个映射 m
定义一个函数 dfs()，它将接收 i、j、grid、idx，
如果 i 和 j 在网格的范围内，并且 grid[i,j] 为 0，则：
返回
grid[i, j] := 0
在 m[idx] 的末尾插入 { i, j }
dfs(i + 1, j, grid, idx)
dfs(i - 1, j, grid, idx)
dfs(i, j - 1, grid, idx)
dfs(i, j + 1, grid, idx)
定义一个函数 norm()，它将接收一个数组 v
定义一个包含 8 行的二维对数组 s
对于初始化 i := 0，当 i < v 的大小，更新（i 增加 1），执行：
x := v[i].first
y := v[i].second
在 s[0] 的末尾插入 { x, y }
在 s[1] 的末尾插入 { x, -y }
在 s[2] 的末尾插入 { - x, y }
在 s[3] 的末尾插入 { - x, -y }
在 s[4] 的末尾插入 { y, x }
在 s[5] 的末尾插入 { y, -x }
在 s[6] 的末尾插入 { - y, x }
在 s[7] 的末尾插入 { - y, -x }
对于初始化 i := 0，当 i < s 的大小，更新（i 增加 1），执行：
对数组 s[i] 进行排序
对于初始化 i := 0，当 i < s 的大小，更新（i 增加 1），执行：
对于初始化 j := 1，当 j < v 的大小，更新（j 增加 1），执行：
s[i, j].first := s[i, j].first - s[i, 0].first
s[i, j].second := s[i, j].second - s[i, 0].second
s[i, 0].first := 0
s[i, 0].second := 0
对数组 s 进行排序
返回 s[0]
从主方法执行以下操作：
定义一个集合 pts
cnt := 1
对于初始化 i := 0，当 i < grid 的大小，更新（i 增加 1），执行：
对于初始化 j := 0，当 j < grid[0] 的大小，更新（j 增加 1），执行：
如果 grid[i, j] 等于 1，则：
（cnt 增加 1）
dfs(i, j, grid, cnt)
将 norm(m[cnt]) 插入 pts
返回 pts 的大小
让我们看看以下实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map < int, vector < pair <int, int> > > m;
void dfs(int i, int j, vector < vector <int> >& grid, int idx){
if (i >= grid.size() || j >= grid[0].size() || i < 0 || !grid[i][j])
return;
grid[i][j] = 0;
m[idx].push_back({ i, j });
dfs(i + 1, j, grid, idx);
dfs(i - 1, j, grid, idx);
dfs(i, j - 1, grid, idx);
dfs(i, j + 1, grid, idx);
}
vector < pair <int, int> > norm(vector < pair < int, int > > v){
vector<vector<pair<int, int> > > s(8);
for (int i = 0; i < v.size(); i++) {
int x = v[i].first;
int y = v[i].second;
s[0].push_back({ x, y });
s[1].push_back({ x, -y });
s[2].push_back({ -x, y });
s[3].push_back({ -x, -y });
s[4].push_back({ y, x });
s[5].push_back({ y, -x });
s[6].push_back({ -y, x });
s[7].push_back({ -y, -x });
}
for (int i = 0; i < s.size(); i++) {
sort(s[i].begin(), s[i].end());
}
for (int i = 0; i < s.size(); i++) {
for (int j = 1; j < v.size(); j++) {
s[i][j].first = s[i][j].first - s[i][0].first;
s[i][j].second = s[i][j].second - s[i][0].second;
}
s[i][0].first = 0;
s[i][0].second = 0;
}
sort(s.begin(), s.end());
return s[0];
}
int numDistinctIslands2(vector<vector<int>>& grid) {
set<vector<pair<int, int> > > pts;
int cnt = 1;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
cnt++;
dfs(i, j, grid, cnt);
pts.insert(norm(m[cnt]));
}
}
}
return pts.size();
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}};
cout << (ob.numDistinctIslands2(v));
}输入
{{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}}输出
1
382 次查看
