图算法DFS与BFS
BFS和DFS代表对图进行遍历，即搜索的算法，搜索算法中常用的只要有两种算法:深度优先遍历(Depth-First-Search : DFS)和广度优先遍历(Breadth-First-Search : BFS)。一个图结构可以用来表示大量现实生活中的问题，比如，道路网络，计算机网络，社交网络，用户身份解析图
①DFS
参考：一文秒杀所有岛屿题目 :: labuladong的算法小抄
200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
如何在二维矩阵中使用 DFS 搜索呢？
// 二维矩阵遍历框架
void dfs(int[][] grid, int i, int j, boolean[][] visited) {
int m = grid.length, n = grid[0].length;
// 超出索引边界
if (i < 0 || j < 0 || i >= m || j >= n) {
return;
}
// 已遍历过 (i, j)
if (visited[i][j]) {
return;
}
// 进入节点 (i, j)
visited[i][j] = true;
dfs(grid, i - 1, j, visited); // 上
dfs(grid, i + 1, j, visited); // 下
dfs(grid, i, j - 1, visited); // 左
dfs(grid, i, j + 1, visited); // 右
visited[i][j] = false;
}
因为二维矩阵本质上是一幅「图」，所以遍历的过程中需要一个 visited 布尔数组防止走回头路
- 目标是找到矩阵中 “岛屿的数量” ，即上下左右相连的
1都被认为是连续岛屿。
算法步骤：每次遇到陆地计数器加1，并把该陆地和该陆地上下左右的陆地变为海水，遍历完之后计数器就是岛屿数量
class Solution {
// 主函数，计算岛屿数量
int numIslands(char[][] grid) {
int res = 0;
int m = grid.length, n = grid[0].length;
// 遍历 grid
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
// 每发现一个岛屿，岛屿数量加一
res++;
// 然后使用 DFS 将岛屿淹了
dfs(grid, i, j);
}
}
}
return res;
}
// 从 (i, j) 开始，将与之相邻的陆地都变成海水
void dfs(char[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// 超出索引边界
return;
}
if (grid[i][j] == '0') {
// 已经是海水了
return;
}
// 将 (i, j) 变成海水
grid[i][j] = '0';
// 淹没上下左右的陆地
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i, j - 1);
}
}
为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢？主要是为了省事，避免维护 visited 数组。
因为 dfs 函数遍历到值为 0 的位置会直接返回，所以只要把经过的位置都设置为 0，就可以起到不走回头路的作用。
733. 图像渲染
面试题 08.10. 颜色填充 - 力扣（Leetcode）
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。
示例 1:
输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。
示例 2:
输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出: [[2,2,2],[2,2,2]]
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
dfs(image, sr, sc, color, image[sr][sc]);
return image;
}
public void dfs(int[][] image, int i, int j, int newColor, int oldColor){
int m = image.length, n = image[0].length;
// 超出边界
if(i < 0 || j < 0 || i >= m || j >= n) {
return;
}
// 连续的初始值才染色
if(image[i][j] != oldColor || newColor == oldColor){
return;
}
// 染色
image[i][j] = newColor;
// 遍历
dfs(image, i - 1, j, newColor, oldColor);
dfs(image, i + 1, j, newColor, oldColor);
dfs(image, i, j - 1, newColor, oldColor);
dfs(image, i, j + 1, newColor, oldColor);
}
}
1254. 统计封闭岛屿的数目
二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。
示例 1：
输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。
示例 2：
输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1
示例 3：
输入：grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
输出：2
力扣第 200 题「 岛屿数量」有两点不同：
1、用 0 表示陆地，用 1 表示海水。
2、让你计算「封闭岛屿」的数目。所谓「封闭岛屿」就是上下左右全部被 1 包围的 0，也就是说靠边的陆地不算作「封闭岛屿」。
那么如何判断「封闭岛屿」呢？其实很简单，把第200题中那些靠边的岛屿排除掉，剩下的不就是「封闭岛屿」了吗？
class Solution {
public int closedIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int j = 0; j < n; j++){
dfs(grid, 0, j); // 把靠上边的岛屿淹掉
dfs(grid, m - 1, j); // 把靠下边的岛屿淹掉
}
for(int i = 0; i < m; i++){
dfs(grid, i, 0); // 把靠上边的岛屿淹掉
dfs(grid, i, n - 1); // 把靠下边的岛屿淹掉
}
int res = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 0){
res++;
dfs(grid, i, j);
}
}
}
return res;
}
// 从 (i, j) 开始，将与之相邻的陆地都变成海水
public void dfs(int[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
// 超出边界
if (i < 0 || j < 0 || i >= m || j >= n) {
return;
}
// 已经是海水了
if (grid[i][j] == 1) {
return;
}
// 将 (i, j) 变成海水
grid[i][j] = 1;
// 淹没上下左右的陆地
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i, j - 1);
}
}
695. 岛屿的最大面积
剑指 Offer II 105. 岛屿的最大面积 - 力扣（Leetcode）
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1：
img
输入：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 。
示例 2：
输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
给 dfs 函数设置返回值，记录每次淹没的陆地的个数
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
int max = 0; // 记录岛屿的最大面积
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
// 淹没岛屿，并更新最大岛屿面积
max = Math.max(max, dfs(grid, i, j));
}
}
}
return max;
}
// 淹没与（i，j） 相邻的陆地，并返回淹没的陆地面积
public int dfs(int[][] grid, int i, int j){
int m = grid.length, n = grid[0].length;
// 超出索引边界
if(i < 0 || j < 0 || i >= m || j >= n){
return 0;
}
// 已经是海水
if(grid[i][j] == 0){
return 0;
}
// 将（i，j）变为海水
grid[i][j] = 0;
// 淹没上下左右的陆地，并统计淹没陆地数量
int sum = 1; // 默认sum为1，如果不是岛屿，则直接返回0，就可以避免预防错误的情况。
sum += dfs(grid, i - 1, j);
sum += dfs(grid, i + 1, j);
sum += dfs(grid, i, j - 1);
sum += dfs(grid, i, j + 1);
return sum;
}
}
1020. 飞地的数量
给你一个大小为 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：
img
输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。
class Solution {
public int numEnclaves(int[][] grid) {
int m = grid.length, n = grid[0].length;
// 去除上下边界陆地
for(int j = 0; j < n; j++){
dfs(grid, 0, j);
dfs(grid, m - 1, j);
}
// 去除左右边界陆地
for(int i = 0; i < m; i++){
dfs(grid, i, 0);
dfs(grid, i, n - 1);
}
int res = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j]== 1){
res++;
}
}
}
return res;
}
// 从 (i, j) 开始，将与之相邻的陆地都变成海水
public void dfs(int[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
// 超出边界
if (i < 0 || j < 0 || i >= m || j >= n) {
return;
}
// 已经是海水了
if (grid[i][j] == 0) {
return;
}
// 将 (i, j) 变成海水
grid[i][j] = 0;
// 淹没上下左右的陆地
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i, j - 1);
}
}
class Solution {
public int numEnclaves(int[][] grid) {
int m = grid.length, n = grid[0].length;
// 去除上下边界陆地
for(int j = 0; j < n; j++){
dfs(grid, 0, j);
dfs(grid, m - 1, j);
}
// 去除左右边界陆地
for(int i = 0; i < m; i++){
dfs(grid, i, 0);
dfs(grid, i, n - 1);
}
int res = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j]== 1){
res += dfs(grid, i, j);
}
}
}
return res;
}
// 淹没与（i，j） 相邻的陆地，并返回淹没的陆地面积
public int dfs(int[][] grid, int i, int j){
int m = grid.length, n = grid[0].length;
// 超出边界
if(i < 0 || j < 0 || i >= m || j >= n){
return 0;
}
// 已是海水
if(grid[i][j] == 0){
return 0;
}
// 将（i，j）变为海水
grid[i][j] = 0;
// 淹没上下左右的陆地，并统计淹没陆地数量
int sum = 1;
sum += dfs(grid, i + 1, j);
sum += dfs(grid, i, j + 1);
sum += dfs(grid, i - 1, j);
sum += dfs(grid, i, j - 1);
return sum;
}
}
噪音传播-华为数存面试
噪音传播-题解
终端产品在进行一项噪音监测实验。若将空实验室平面图视作一个N*M的二维矩阵（左上角为[0,0]）。工作人员在实验室内设置了若干噪音源，并以[噪音源所在行，噪音源所在列，噪音值]的形式记录于二维数组noise中。
噪音沿相邻8个方向传播，在传播过程中，噪音值（单位为分贝）逐级递减1分贝，直至分贝削弱至1（即噪音源覆盖区域边缘噪音分贝为1）;
若同一格被多个噪音源的噪音覆盖，检测结果不叠加，仅保留较大的噪音值（噪音源所在格也可能被其他噪音源的噪声传播所覆盖）。
在所有噪音源开启且持续传播情况稳定后，请监测每格噪音分贝数并返回他们的总和。
注意：
除噪音源以外的所有格初始值为0分贝；不考虑墙面反射。
示例1：
输入：n=5,m=6,noise=[[3,4,3],[1,1,4]]
输出：63
class Main {
public static void main(String[] args) {
int[][] noise = {{3,4,3}, {1,1,4}};
System.out.println(spreadNoise(5, 6, noise));
}
public static int spreadNoise(int n, int m, int[][] noise) {
int[][] grid = new int[n][m];
for (int[] num: noise) {
dfs(grid, num[0], num[1], num[2]);
}
// 统计结果
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sum += grid[i][j];
}
}
return sum;
}
// 噪声填充
// 将（i，j）的 8 个方向填充数据
public static void dfs(int[][] grid, int row, int col, int val){
int m = grid.length, n = grid[0].length;
// 超出边界
if (row < 0 || col < 0 || row >= m || col >= n) {
return;
}
// 循环结束（val为0 或 保留较大的噪音值）
if (val == 0 || grid[row][col] >= val) {
return;
}
// 记录值
grid[row][col] = val;
// 沿8个方向扩散
dfs(grid, row + 1, col, val - 1);
dfs(grid, row - 1, col, val - 1);
dfs(grid, row, col + 1, val - 1);
dfs(grid, row, col - 1, val - 1);
dfs(grid, row + 1, col + 1, val - 1);
dfs(grid, row + 1, col - 1, val - 1);
dfs(grid, row - 1, col + 1, val - 1);
dfs(grid, row - 1, col - 1, val - 1);
}
}
79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(dfs(board, i, j, word, 0, visited)){
return true;
}
}
}
return false;
}
// 从 (i, j) 开始向四周搜索，试图匹配 word[p..]
boolean dfs(char[][] board, int i, int j, String word, int p, boolean[][] visited) {
int m = board.length, n = board[0].length;
if(p == word.length()){
return true;
}
if (i < 0 || j < 0 || i >= m || j >= n) {
// 超出索引边界
return false;
}
if(board[i][j] != word.charAt(p)){
return false;
}
if (visited[i][j]) {
// 已遍历过 (i, j)
return false;
}
// 进入节点 (i, j)
visited[i][j] = true;
boolean t = dfs(board, i - 1, j, word, p + 1, visited); // 上
boolean b = dfs(board, i + 1, j, word, p + 1, visited); // 下
boolean l = dfs(board, i, j - 1, word, p + 1, visited); // 左
boolean r = dfs(board, i, j + 1, word, p + 1, visited); // 右
visited[i][j] = false;
return t || b || l || r;
}
}
994. 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
对于二维网格 grid 来说，当遍历到腐烂的
