695. 岛屿的最大面积

力扣题目链接(opens new window)

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

• 输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
• 输出：6
• 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

思路：广度优先和深度优先皆可，遍历的时候计数，然后取最大数量即可

class Solution {
public://深度优先版本int count=0;int result =0;int dir[4][2]={0,1,1,0,-1,0,0,-1};void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){for(int i=0;i<4;i++){int nextx= x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){visited[nextx][nexty]=true;count++;dfs(grid,visited,nextx,nexty);}}}int maxAreaOfIsland(vector<vector<int>>& grid) {int n=grid.size(); int m=grid[0].size();vector<vector<bool>>visited=vector<vector<bool>>(n,vector<bool>(m,false));for(int i=0;i<n;i++){for(int j=0; j<m;j++){if(!visited[i][j]&&grid[i][j]==1){count=1;//遇到陆地先计数visited[i][j]=true;dfs(grid,visited,i,j);result=max(result,count);}}}return result;}
};

//广度优先版本
class Solution {
public:int count=0;int result =0;int dir[4][2]={0,1,1,0,-1,0,0,-1};void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){queue<int>que;que.push(x);que.push(y);visited[x][y]=true;count++;while(!que.empty()){int xx=que.front(); que.pop();int yy=que.front(); que.pop();for(int i=0;i<4;i++){int nextx=  xx+dir[i][0];int nexty=  yy+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){visited[nextx][nexty]=true;count++;que.push(nextx);que.push(nexty);}}}}int maxAreaOfIsland(vector<vector<int>>& grid) {int n=grid.size(); int m=grid[0].size();vector<vector<bool>>visited=vector<vector<bool>>(n,vector<bool>(m,false));for(int i=0;i<n;i++){for(int j=0; j<m;j++){if(!visited[i][j]&&grid[i][j]==1){count=0;visited[i][j]=true;dfs(grid,visited,i,j);result=max(result,count);}}}return result;}
};

1020. 飞地的数量

力扣链接(opens new window)

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

• 输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
• 输出：3
• 解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

• 输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
• 输出：0
• 解释：所有 1 都在边界上或可以到达边界

思路：本题要求找到不靠边的陆地面积，那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图的时候，统计此时还剩下的陆地就可以了。

遍历周边：分别遍历最左列（grid[i][0]),最右列（grid[i][m-1]),最上行（grid[0][j]),最下行（grid[n-1][j]),同时进行搜索，在搜索过程中将其置0。

class Solution {
public://深度优先搜索int dir[4][2]={1,0,0,1,-1,0,0,-1};//四个方向int count;void dfs(vector<vector<int>>& grid, int x, int y){grid[x][y]=0;count++;for(int i=0; i<4; i++){int nextx= x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(grid[nextx][nexty]==1){// count++;// grid[nextx][nexty]=0;dfs(grid, nextx, nexty);}}return;}int numEnclaves(vector<vector<int>>& grid) {// int count=0;int n=grid.size();//行数int m=grid[0].size();//列数//遍历周边for(int i=0;i<n;i++){if(grid[i][0])dfs(grid, i,0);//遍历最左列if(grid[i][m-1])dfs(grid,i, m-1);//遍历最右列}for(int j=0; j<m;j++){if(grid[0][j])dfs(grid, 0, j);//遍历最上行if(grid[n-1][j])dfs(grid,n-1, j);//遍历最底行}//遍历整个网格，并计数count= 0;for(int i=0; i<n; i++){for(int j=0; j<m;j++){if(grid[i][j]){// count++;dfs(grid,i, j);}}}return count;}
};

//广度优先搜索
class Solution {
public:int count =0;int dir[4][2]={0,1,1,0,0,-1,-1,0};void bfs(vector<vector<int>>& grid, int x, int y){queue<pair<int,int>>que;que.push({x,y});count++;grid[x][y]=0;while(!que.empty()){pair<int,int>cur=que.front();que.pop();for(int i=0;i<4;i++){int nextx=cur.first+dir[i][0];int nexty=cur.second+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(grid[nextx][nexty]){que.push({nextx,nexty});count++;grid[nextx][nexty]=0;}}}return;}int numEnclaves(vector<vector<int>>& grid) {int n=grid.size();//行数int m=grid[0].size();//列数//遍历周边并置0for(int i=0;i<n;i++){if(grid[i][0])bfs(grid,i,0);//遍历最左列if(grid[i][m-1])bfs(grid,i,m-1);//遍历最右列}for(int j=0;j<m;j++){if(grid[0][j]) bfs(grid,0,j);//遍历第一行if(grid[n-1][j]) bfs(grid,n-1,j);//遍历最后一行}//重新遍历整个网格并计算count=0;for(int i=0; i<n;i++) {for(int j=0;j<m;j++){if(grid[i][j]){bfs(grid,i,j);}}}return count;}
};

130. 被围绕的区域

题目链接(opens new window)

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

• 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
• 输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
• 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的

思路：和上一题类似，只是需要把’飞地‘改为”X"

先广度优先或深度优先遍历周边，把周边的X换为'A'，然后两个for循环遍历整个grid,遇到'A'换成’O',遇到'O'换成‘X'

//广度优先搜索
class Solution {
public:int dir[4][2]={0,1,1,0,0,-1,-1,0};void dfs(vector<vector<char>>& board, int x, int y){board[x][y]='A';for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=board.size()||nexty<0||nexty>=board[0].size())continue;if(board[nextx][nexty]=='O'){dfs(board,nextx,nexty);}}return;}void solve(vector<vector<char>>& board) {int n=board.size();//行数int m=board[0].size();//列数//遍历周边，把周边的'O'换成’A‘for(int i=0;i<n;i++){if(board[i][0]=='O')dfs(board,i,0);//遍历最左列if(board[i][m-1]=='O')dfs(board,i,m-1);//遍历最右列}for(int j=0;j<m;j++){if(board[0][j]=='O')dfs(board,0,j);//最上行if(board[n-1][j]=='O')dfs(board,n-1,j);//最下行}//遍历整个网格并替换for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]=='O')board[i][j]='X';if(board[i][j]=='A') board[i][j]='O';}}}
};

class Solution {
public:int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};void bfs(vector<vector<char>>& board, int x, int y) {queue<pair<int, int>> que;que.push({x, y});board[x][y]='A';while (!que.empty()) {pair<int, int> cur = que.front();que.pop();for (int i = 0; i < 4; i++) {int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if (nextx < 0 || nextx >= board.size() || nexty < 0 ||nexty >= board[0].size())continue;if (board[nextx][nexty] == 'O') {board[nextx][nexty] = 'A';// cout<<"board[nextx][nexty]:"<<board[nextx][nexty]<<endl;que.push({nextx, nexty});}}}}void solve(vector<vector<char>>& board) {int n = board.size();int m = board[0].size();// 遍历周边for (int i = 0; i < n; i++) {if (board[i][0] == 'O')bfs(board, i, 0);if (board[i][m - 1] == 'O')bfs(board, i, m - 1);}for (int j = 0; j < m; j++) {if (board[0][j] == 'O')bfs(board, 0, j);if (board[n - 1][j] == 'O')bfs(board, n - 1, j);}// 遍历整个网格并替换for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// cout<<"before: "<<board[i][j]<<endl;if (board[i][j] == 'O')board[i][j] = 'X';if (board[i][j] == 'A')board[i][j] = 'O';}}}
};

 参考：代码随想录