LeetCode 694. 不同岛屿的数量（BFS/DFS+set）

文章目录

• • 1. 题目
  • 2. 解题
  • • 2.1 BFS
    • 2.2 DFS

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

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 694. 不同岛屿的数量（BFS/DFS+set）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。