桐乡微网站建设公司wordpress 经典博客主题

Leetcode 1254

题意

给定一个m*n的矩阵含有0和1，1代表水，0代表陆地，岛屿是陆地的集合，如果一个岛屿和四个方向的边界相连，则不算封闭岛屿。求有多少个封闭的岛屿。

题目链接

https://leetcode.com/problems/number-of-closed-islands/

思路

从边界上的0开始用dfs向四个方向遍历，把这些0形成的岛屿都遍历完成，这样就能排除和边界相连的岛屿。然后再从没有遍历过的0开始用dfs向四个方向遍历，并且计数。这些岛屿就是封闭的岛屿（参考number of islands）

题解

class Solution {
public:int m;int n;int closedIsland(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int res = 0;vector<vector<bool>> vis(m, vector<bool>(n, false));for(int i = 0; i < m; i++) {if(grid[i][0] == 0 && !vis[i][0]) {dfs(grid, vis, i, 0);}if(grid[i][n-1] == 0 && !vis[i][n-1]) {dfs(grid, vis, i, n-1);}}for(int i = 0; i < n; i++) {if(grid[0][i] == 0 && !vis[0][i]) {dfs(grid, vis, 0, i);}if(grid[m-1][i] == 0 && !vis[m-1][i]) {dfs(grid, vis, m-1, i);}}for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 0 && !vis[i][j]) {dfs(grid, vis, i, j);res++;}}}return res;}void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {vis[x][y] = true;int dk[] = {-1, 0, 1, 0, -1};for(int i = 0; i < 4; i++) {int dx = x + dk[i];int dy = y + dk[i+1];if(dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && grid[dx][dy] == 0) {dfs(grid, vis, dx, dy);}}}
};

时间复杂度：$O(mn)$ m为给定矩阵的长度，n为给定矩阵的宽度
空间复杂度：$O(mn)$ m为给定矩阵的长度，n为给定矩阵的宽度

Leetcode 1020

思路

和Leetcode 1254一样，只是换壳的Number of Closed Islands + Max Area of Island，不赘述了。

题解

class Solution {
public:int m;int n;int numEnclaves(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int res = 0;vector<vector<bool>> vis(m, vector<bool>(n, false));for(int i = 0; i < m; i++) {if(grid[i][0] == 1 && !vis[i][0]) {dfs(grid, vis, i, 0);}if(grid[i][n-1] == 1 && !vis[i][n-1]) {dfs(grid, vis, i, n-1);}}for(int i = 0; i < n; i++) {if(grid[0][i] == 1 && !vis[0][i]) {dfs(grid, vis, 0, i);}if(grid[m-1][i] == 1 && !vis[m-1][i]) {dfs(grid, vis, m-1, i);}}for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 1 && !vis[i][j]) {res += dfs(grid, vis, i, j);}}}return res;}int dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {vis[x][y] = true;int area = 1;int dk[] = {-1, 0, 1, 0, -1};for(int i = 0; i < 4; i++) {int dx = x + dk[i];int dy = y + dk[i+1];if(dx >= 0 && dx < m && dy >= 0 && dy < n && grid[dx][dy] == 1 && !vis[dx][dy]) {area += dfs(grid, vis, dx, dy);}}return area;}
};

时间复杂度：$O(mn)$ m为给定矩阵的长度，n为给定矩阵的宽度
空间复杂度：$O(mn)$ m为给定矩阵的长度，n为给定矩阵的宽度