資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
