695.島嶼的最大面積

文檔講解：代碼隨想錄
視頻講解：
狀態

采用bfs，這道題相較于之前的題變為了求島嶼的最大面積。那就說明我們每遇到一個新的島嶼就要重新計算一個面積，然后和之前的最大面積比較。

class Solution {
private:int dir[4][2] = {0,1,1,0,-1,0,0,-1};int count;
public:void bfs(vector<vector<int>>& grid, vector<vector<bool>>& vistied, int x,int y){queue<pair<int,int>> check;check.push({x,y});visitied[x][y] = true;while(!check.empty()){pair<int,int> cur = check.front();check.pop();int curx = cur.first;int cury = cur.second;for(int i=0;i<4;i++){int nextx = curx+dir[i][0];int nexty = cury+dir[i][1];//如果超過范圍那么跳過if(nextx < 0 || nextx >= grid.size() || nexty <0 || nexty>=grid[0].size()) continue;//沒有被訪問過，且為1if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){visited[nextx][nexty] = true;//面積+1count++;check.push({nextx,nexty});} }}}
public：int maxAreaOfIsland(vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();vector<vector<bool>> visited(n,vector<bool>(m,false));int res = 0;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){//第一次bfs//當遇到沒有被訪問過，且為1說明是一塊新的陸地if(!visited[i][j] && grid[i][j] == 1){//重置count;count = 1;bfs(grid,visited,i,j);res = max(count,res);}}}return res;}
};

1020.飛地的數量

文檔講解：代碼隨想錄
視頻講解：
狀態

將邊緣陸地形成的島嶼全部變為海洋后，再重新遍歷整個圖，得到的就是飛地。

class Solution {
private:int dir[4][2] = {0,1,1,0,-1,0,0,-1};int res = 0;
public:void bfs(vector<vector<int>>& grid,int x,int y){queue<pair<int,int>> check;check.push({x,y});grid[x][y] = 0;res++;while(!check.empty()){pair<int,int> cur = check.front();check.pop();int curx = cur.first;int cury = cur.second;for(int i = 0;i<4;i++){int nextx = curx+dir[i][0];int nexty = cury+dir[i][1];if(nextx <0 || nextx>=grid.size() || nexty<0 || nexty>=grid[0].size()){continue;}if(grid[nextx][nexty] == 1){res++;check.push({nextx,nexty});grid[nextx][nexty] = 0;}}}}
public:int numEnclaves(vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();//從左岸和右岸向中間淹沒for(int i = 0;i<n;i++){if(grid[i][0] == 1) bfs(grid,i,0);if(grid[i][m-1] == 1) bfs(grid,i,m-1);}//從上面和下面向中間淹沒for(int j = 0;j<m;j++){if(grid[0][j] == 1) bfs(grid,0,j);if(grid[n-1][j] == 1) bfs(grid,n-1,j);}res = 0;//統計剩余單元島嶼個數for(int i = 0;i<n;i++){for(int j= 0;j<m;j++){if(grid[i][j] == 1){bfs(grid,i,j);}}}return res;}
};