算法学习——LeetCode力扣图论篇2

算法学习——LeetCode力扣图论篇2

1020. 飞地的数量

1020. 飞地的数量 - 力扣（LeetCode）

描述

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

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

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

示例

示例 1：

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

示例 2：

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

提示

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] 的值为 0 或 1

代码解析

class Solution {
public:int result = 0 , tmp_size = 1;int m =0 ,n=0;bool borad_flag = false;int dir[4][2] = {0,1, 0,-1 , -1,0 , 1,0};void dfs(vector<vector<int>>& grid , vector<vector<bool>> &path , int x , int y){for(int i=0 ; i<4 ;i++){int next_x = x + dir[i][0];int next_y = y + dir[i][1];if(next_x<0||next_x>=m||next_y<0||next_y>=n){borad_flag = true;continue;}if( path[next_x][next_y] == false && grid[next_x][next_y] == 1) {   tmp_size++;path[next_x][next_y] = true;dfs(grid,path,next_x,next_y);}}return;}int numEnclaves(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();vector<vector<bool>> path( m , vector<bool>( n ,false) );for(int i=0 ; i<m ;i++){for(int j=0 ; j<n ;j++){if(path[i][j] == false && grid[i][j] == 1){tmp_size = 1;borad_flag = false;path[i][j] = true;dfs(grid,path,i,j);if(borad_flag == false ) result += tmp_size;}}}return result;}
};

130. 被围绕的区域

130. 被围绕的区域 - 力扣（LeetCode）

描述

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

示例

示例 1：

输入：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’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [[“X”]]
输出：[[“X”]]

提示

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 ‘X’ 或 ‘O’

代码解析

class Solution {
public:int m=0 , n=0;bool board_flag = false;int dir[4][2] = {0,-1,0,1,-1,0,1,0};void dfs(vector<vector<char>>& board ,  vector<vector<bool>> &path ,int x , int y ,bool exchange){   for(int i=0 ; i<4 ;i++){int next_x = x + dir[i][0];int next_y = y + dir[i][1];if(next_x<0 || next_x >= m || next_y<0||next_y>=n){board_flag = true;continue;}if(exchange == false && board[next_x][next_y] == 'O' && path[next_x][next_y] == false){path[next_x][next_y] = true;dfs(board,path,next_x,next_y,exchange);}if(exchange == true && board[next_x][next_y] == 'O'){board[next_x][next_y] = 'X';dfs(board,path,next_x,next_y,exchange);}}}void solve(vector<vector<char>>& board) {m = board.size();n = board[0].size();vector<vector<bool>> path(m,vector<bool>(n,false));for(int i=0 ; i<m ;i++){for(int j=0 ; j<n ;j++){if(board[i][j] == 'O' && path[i][j] == false){board_flag = false;path[i][j] = true;dfs(board,path,i,j,false);if(board_flag == false){board[i][j] = 'X';dfs(board,path,i,j,true);} }}}}
};

827. 最大人工岛

827. 最大人工岛 - 力扣（LeetCode）

描述

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

提示

n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] 为 0 或 1

代码解析

class Solution {
public:int m = 0 , n = 0;int dir[4][2] = {0,-1,0,1,-1,0,1,0};int tmp_sum = 1 , bolck_num = 1;void dfs(vector<vector<int>>& grid ,vector<vector<bool>> &path , int x ,int y ,int num ){for(int i=0 ; i<4 ;i++){int next_x = x + dir[i][0];int next_y = y + dir[i][1];if(next_x<0||next_x>=m||next_y<0||next_y>=n) continue;if(grid[next_x][next_y] == 1 && path[next_x][next_y] == false){tmp_sum++;grid[next_x][next_y] = num;dfs(grid,path,next_x,next_y,num);}}}int largestIsland(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();vector<vector<bool>> path(m,vector<bool>(n,false));map<int,int> my_map;for(int i=0 ; i<m ;i++){for(int j=0 ; j<n ;j++){if(grid[i][j] == 1 && path[i][j] == false){bolck_num++;path[i][j] = true;grid[i][j] = bolck_num;tmp_sum=1;dfs(grid,path,i,j,bolck_num);my_map[bolck_num] = tmp_sum;}}}int result = 0 , tmp_result = 1;for(int i=0 ; i<m ;i++){for(int j=0 ; j<n ;j++){if(grid[i][j] == 0 && path[i][j] == false){path[i][j] = true;tmp_result = 1;set<int> my_set;for(int k=0 ; k<4 ;k++){int next_x = i + dir[k][0];int next_y = j + dir[k][1];if(next_x<0||next_x>=m||next_y<0||next_y>=n) continue;if(grid[next_x][next_y] != 0 ) my_set.insert(grid[next_x][next_y]);}for(auto it = my_set.begin() ; it!=my_set.end();it++) tmp_result += my_map[*it];my_set.clear();if(tmp_result > result) result = tmp_result;}}}if(result == 0) return m*n;return result;}
};