如何做拉勾勾网站,如何制作企业内部网站,免费软件视频,百度提交链接多久会被收录文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
给定一个非空01二维数组表示的网格#xff0c;一个岛屿由四连通#xff08;上、下、左、右四个方向#xff09;的 1 组成#xff0c;你可以认为网格的四周被海水包围。
请你计算这个网格中共有多少个形状不同的岛屿。 两个岛…
文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
给定一个非空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(vectorvectorint 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;vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};setvectorvectorint s;for(i 0; i m; i){for(j 0; j n; j){if(grid[i][j] 0)continue;x0 i, y0 j;queuevectorint q;vectorvectorint 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(nx0 nxm ny0 nyn 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 {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};int m, n;setvectorvectorint s;
public:int numDistinctIslands(vectorvectorint 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;vectorvectorint path;grid[i][j] 0;//访问过DFS(grid,i,j,i,j,path);s.insert(path);}}return s.size();}void DFS(vectorvectorint grid, int x0, int y0, int x, int y, vectorvectorint 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(nx0 nxm ny0 nyn 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阿明一起加油、一起学习进步
