云南火电建设有限公司网站,策划网站建设价格,医疗行业网站策划,做网站会犯法吗算法学习——LeetCode力扣图论篇2 1020. 飞地的数量
1020. 飞地的数量 - 力扣#xff08;LeetCode#xff09;
描述
给你一个大小为 m x n 的二进制矩阵 grid #xff0c;其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相…算法学习——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 ,n0;bool borad_flag false;int dir[4][2] {0,1, 0,-1 , -1,0 , 1,0};void dfs(vectorvectorint grid , vectorvectorbool path , int x , int y){for(int i0 ; i4 ;i){int next_x x dir[i][0];int next_y y dir[i][1];if(next_x0||next_xm||next_y0||next_yn){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(vectorvectorint grid) {m grid.size();n grid[0].size();vectorvectorbool path( m , vectorbool( n ,false) );for(int i0 ; im ;i){for(int j0 ; jn ;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 m0 , n0;bool board_flag false;int dir[4][2] {0,-1,0,1,-1,0,1,0};void dfs(vectorvectorchar board , vectorvectorbool path ,int x , int y ,bool exchange){ for(int i0 ; i4 ;i){int next_x x dir[i][0];int next_y y dir[i][1];if(next_x0 || next_x m || next_y0||next_yn){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(vectorvectorchar board) {m board.size();n board[0].size();vectorvectorbool path(m,vectorbool(n,false));for(int i0 ; im ;i){for(int j0 ; jn ;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(vectorvectorint grid ,vectorvectorbool path , int x ,int y ,int num ){for(int i0 ; i4 ;i){int next_x x dir[i][0];int next_y y dir[i][1];if(next_x0||next_xm||next_y0||next_yn) 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(vectorvectorint grid) {m grid.size();n grid[0].size();vectorvectorbool path(m,vectorbool(n,false));mapint,int my_map;for(int i0 ; im ;i){for(int j0 ; jn ;j){if(grid[i][j] 1 path[i][j] false){bolck_num;path[i][j] true;grid[i][j] bolck_num;tmp_sum1;dfs(grid,path,i,j,bolck_num);my_map[bolck_num] tmp_sum;}}}int result 0 , tmp_result 1;for(int i0 ; im ;i){for(int j0 ; jn ;j){if(grid[i][j] 0 path[i][j] false){path[i][j] true;tmp_result 1;setint my_set;for(int k0 ; k4 ;k){int next_x i dir[k][0];int next_y j dir[k][1];if(next_x0||next_xm||next_y0||next_yn) 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;}
};
