LeetCode 694. 不同岛屿的数量（BFS/DFS+set）
LeetCode 694. 不同岛屿的数量（BFS/DFS+set）
Michael阿明
发布于 2021-02-19 09:55:10
发布于 2021-02-19 09:55:10
文章被收录于专栏：Michael阿明学习之路
文章目录
1. 题目
给定一个非空01二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。
请你计算这个网格中共有多少个形状不同的岛屿。 两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。
样例 1:
11000
11000
00011
00011
给定上图，返回结果 1。
样例 2:
11011
10000
00001
11011
给定上图，返回结果 3。
注意:
11
1
和
1
11
是不同的岛屿，因为我们不考虑旋转、翻转操作。
注释 : 二维数组每维的大小都不会超过50。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-distinct-islands 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 记录开始BFS或DFS的起点，后续点跟起点做差，存储路径到set中去重，返回 set 的大小
2.1 BFS
class Solution {
public:
int numDistinctIslands(vector<vector<int>>& grid) {
if(grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size(), i, j, k, x, y, x0, y0, nx, ny;
vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
set<vector<vector<int>>> s;
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
if(grid[i][j] == 0)
continue;
x0 = i, y0 = j;
queue<vector<int>> q;
vector<vector<int>> path;
q.push({x0, y0});
grid[x0][y0] = 0;//访问过
while(!q.empty())
{
x = q.front()[0];
y = q.front()[1];
path.push_back({x-x0, y-y0});//路径记录相对坐标
q.pop();
for(k = 0; k < 4; ++k)
{
nx = x + dir[k][0];
ny = y + dir[k][1];
if(nx>=0 && nx<m && ny>=0 && ny<n && grid[nx][ny])
{
q.push({nx, ny});
grid[nx][ny] = 0;//访问过
}
}
}
s.insert(path);
}
}
return s.size();
}
};172 ms 43.6 MB
2.2 DFS
class Solution {
vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
int m, n;
set<vector<vector<int>>> s;
public:
int numDistinctIslands(vector<vector<int>>& grid) {
if(grid.empty() || grid[0].empty()) return 0;
m = grid.size(), n = grid[0].size();
for(int i = 0, j; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
if(grid[i][j] == 0)
continue;
vector<vector<int>> path;
grid[i][j] = 0;//访问过
DFS(grid,i,j,i,j,path);
s.insert(path);
}
}
return s.size();
}
void DFS(vector<vector<int>>& grid, int x0, int y0, int x, int y, vector<vector<int>>& path)
{
path.push_back({x-x0, y-y0});//路径记录相对坐标
int k, nx, ny;
for(k = 0; k < 4; ++k)
{
nx = x + dir[k][0];
ny = y + dir[k][1];
if(nx>=0 && nx<m && ny>=0 && ny<n && grid[nx][ny])
{
grid[nx][ny] = 0;//访问过
DFS(grid, x0, y0, nx, ny, path);
}
}
}
};128 ms 35.8 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/07/17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
