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