假设我们有一个二进制的2D阵列网格，这里的一个岛是一组4（水平或垂直）连接的1（土地）。我们可以假定网格的所有四个边缘都被水包围。我们必须计算不同岛屿的数量。
当一个岛可以平移（而不旋转或反射）以等于另一个时，则认为该岛与另一个岛相同。
所以，如果输入像
| 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，网格，温度，'d'）
dfs（x，y-1，grid，temp，'u'）
temp：= temp连接'b'
从主要方法中执行以下操作-
ret：= 0
定义一组参观
对于初始化i：= 0，当i <网格的行数时，更新（将i增加1），执行-
如果grid [i，j]不为零，则-
（增加ret 1）
将辅助插入访问
aux：=空字符串
dfs（i，j，grid，aux，'s'）
如果未访问辅助，则-
对于初始化j：= 0，当j <网格的col计数时，更新（将j增加1），执行-
返回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