文章目錄

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

1. 題目

有一個二維矩陣 grid ，每個位置要么是陸地（記號為 0 ）要么是水域（記號為 1 ）。

我們從一塊陸地出發(fā)，每次可以往上下左右 4 個方向相鄰區(qū)域走，能走到的所有陸地區(qū)域，我們將其稱為一座「島嶼」。

如果一座島嶼 完全 由水域包圍，即陸地邊緣上下左右所有相鄰區(qū)域都是水域，那么我們將其稱為 「封閉島嶼」。

請返回封閉島嶼的數目。

示例 1：

輸入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] 輸出：2 解釋： 灰色區(qū)域的島嶼是封閉島嶼，因為這座島嶼完全被水域包圍（即被 1 區(qū)域包圍）。 示例 2：

輸入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] 輸出：1 示例 3： 輸入：grid = [[1,1,1,1,1,1,1],[1,0,0,0,0,0,1],[1,0,1,1,1,0,1],[1,0,1,0,1,0,1],[1,0,1,1,1,0,1],[1,0,0,0,0,0,1],[1,1,1,1,1,1,1]] 輸出：2提示： 1 <= grid.length, grid[0].length <= 100 0 <= grid[i][j] <=1

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-closed-islands
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權，非商業(yè)轉載請注明出處。

2. 解題

• 套路解題：題目可以總結為，搜索的過程中，不能出界，出界了就不算封閉島嶼

2.1 DFS

class Solution {vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};int m,n; public:int closedIsland(vector<vector<int>>& grid) {//可以總結為，找的過程中，不能出界，出界的島嶼不算int i, j, island = 0;m = grid.size(), n = grid[0].size();bool out;for(i = 0; i < m; ++i){for(j = 0; j < n; ++j){if(grid[i][j] == 0)//陸地{out = false;//出界了嗎？grid[i][j] = 1;//訪問過了，無需回溯，直接改dfs(grid,i,j,out);if(!out)//沒有出界island++;}}}return island;}void dfs(vector<vector<int>>& grid, int i, int j, bool& out){int x, y, k;for(k = 0; k < 4; ++k){x = i+dir[k][0];y = j+dir[k][1];if(x>=0 && x<m && y>=0 && y<n){ //在范圍內，是陸地if(grid[x][y] == 0){grid[x][y] = 1;//訪問過dfs(grid,x,y,out);}}else//不在范圍內out = true;}} };

2.2 BFS

class Solution {vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};int m,n; public:int closedIsland(vector<vector<int>>& grid) {//可以總結為，找的過程中，不能出界，出界的島嶼不算int i, j, island = 0, x, y, k;m = grid.size(), n = grid[0].size();queue<pair<int,int> > q;pair<int,int> tp;bool out;for(i = 0; i < m; ++i){for(j = 0; j < n; ++j){if(grid[i][j] == 0)//陸地{out = false;grid[i][j] = 1;//訪問過了，無需回溯，直接改q.push({i,j});while(!q.empty()){tp = q.front();q.pop();for(k = 0; k < 4; ++k){x = tp.first+ dir[k][0];y = tp.second + dir[k][1];if(x>=0 && x<m && y>=0 && y<n){ //在范圍內，是陸地if(grid[x][y] == 0){grid[x][y] = 1;//訪問過q.push({x,y});}}else//不在范圍內out = true;}}if(!out)island++;}}}return island;} };

總結

以上是生活随笔為你收集整理的LeetCode 1254. 统计封闭岛屿的数目（图的BFS DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。