文章目錄

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

1. 題目

給出一個二維數組 A，每個單元格為 0（代表海）或 1（代表陸地）。

移動是指在陸地上從一個地方走到另一個地方（朝四個方向之一）或離開網格的邊界。

返回網格中無法在任意次數的移動中離開網格邊界的陸地單元格的數量。

示例 1： 輸入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] 輸出：3 解釋： 有三個 1 被 0 包圍。一個 1 沒有被包圍，因為它在邊界上。示例 2： 輸入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] 輸出：0 解釋： 所有 1 都在邊界上或可以到達邊界。提示： 1 <= A.length <= 500 1 <= A[i].length <= 500 0 <= A[i][j] <= 1 所有行的大小都相同

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

2. 解題

2.1 BFS

• 利用隊列bfs，bool 變量記錄是否接觸邊界
• 接觸，bfs返回0，不接觸，返回陸地數量

class Solution {vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};int m, n, x, y, k;int count;bool out;queue<pair<int,int>> q;pair<int,int> tp; public:int numEnclaves(vector<vector<int>>& A) {m = A.size(), n = A[0].size();int land = 0, i, j;for(i = 0; i < m; i++){for(j = 0; j < n; j++){if(A[i][j] == 1)//陸地{land += bfs(A,i,j);}}}return land;}int bfs(vector<vector<int>>& A, int i, int j) {count = 0;A[i][j] = 0;//訪問過了count++;//陸地計數+1q.push({i,j});bool out = (i==0||i==m-1||j==0||j==n-1);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 && A[x][y]==1){A[x][y] = 0;count++;q.push({x,y});if(!out && (x==0||x==m-1||y==0||y==n-1))out = true;}}}if(out)return 0;return count;} };

2.2 DFS

class Solution {vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};int m, n; public:int numEnclaves(vector<vector<int>>& A) {m = A.size(), n = A[0].size();int land = 0, i, j;bool out;for(i = 0; i < m; i++){for(j = 0; j < n; j++){if(A[i][j] == 1)//陸地{out = (i==0||i==m-1||j==0||j==n-1);land += dfs(A,i,j,out);}}}return land;}int dfs(vector<vector<int>>& A, int i, int j, bool& out) {int x, y, k, count = 0;A[i][j] = 0;//訪問過了count++;//陸地計數+1for(k = 0; k < 4; ++k){x = i + dir[k][0];y = j + dir[k][1];if(x>=0 && x<m && y>=0 && y<n && A[x][y]==1){A[x][y] = 0;if(!out && (x==0||x==m-1||y==0||y==n-1))out = true;count += dfs(A,x,y,out);}}if(out)return 0;return count;} };

總結

以上是生活随笔為你收集整理的LeetCode 1020. 飞地的数量（图的BFS/DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

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