C ++中不同岛屿II的数量
假设我们有一个称为网格的非空2D二进制数组，这里的一个岛是一组4方向相连的1（代表陆地）。我们还可以假设网格的所有四个边缘都被水包围。
我们必须计算不同岛屿的数量。如果一个岛具有相同的形状，或者仅旋转90、180或270度或反射左/右方向或上/下方向后具有相同的形状，则认为该岛与另一个岛相同。
所以，如果输入像
那么输出将为1
为了解决这个问题，我们将遵循以下步骤-
定义一张映射
定义一个函数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，网格，idx）
定义一个函数norm()，这将需要一个数组v
对于初始化j：=1，当j<v的大小时，更新（将j增加1），做-
s[i，0].first：=0
s[i，0].second：=0
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]排序
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}
定义一个8行对的2D数组
对于初始化i：=0，当i<v的大小时，更新（将i增加1），执行-
对于初始化i：=0，当i<s的大小时，更新（将i增加1），执行-
对于初始化i：=0，当i<s的大小时，更新（将i增加1），执行-
对数组进行排序
返回s[0]
从主要方法中执行以下操作-
定义一组点
中位数：=1
对于初始化i：=0，当i<网格大小时，更新（将i增加1），执行-
如果grid[i，j]与1相同，则-
（将cnt增加1）
dfs(i,j,grid,cnt)
将规范（m[cnt]）插入点
对于初始化j：=0，当j<grid[0]的大小时，更新（将j增加1），执行＆miuns;。
点的返回大小
让我们看下面的实现以更好地理解-
示例
#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