题目一： 图像渲染

1. 题⽬链接：

https://leetcode.cn/problems/flood-fill/description/

2. 题⽬描述：

有⼀幅以 m x n 的⼆维整数数组表⽰的图画 image ，其中 image[i][j] 表⽰该图画的像素值⼤⼩。 你也被给予三个整数
sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进⾏ 上⾊填充 。 为了完成 上⾊⼯作
，从初始像素开始，记录初始坐标的 上下左右四个⽅向上 像素值与初始坐标相同 的相连像素点，接着再记录这四个⽅向上符合条件的像素点与他们对应
四个⽅向上 像素值与初始坐 标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜⾊值改为 newColor 。 最后返回
经过上⾊渲染后的图像 。

3. 算法思路：

可以利⽤「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可，本题这里采取的解法是利用队列+深搜哦。

4.代码

class Solution 
{int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};public int[][] floodFill(int[][] image, int sr, int sc, int color) {int prev = image[sr][sc]; // 统计刚开始的颜⾊ if(prev == color) return image; // 处理边界情况 int m = image.length, n = image[0].length;Queue<int[]> q = new LinkedList<>();q.add(new int[]{sr, sc});while(!q.isEmpty()){int[] t = q.poll();int a = t[0], b = t[1];image[a][b] = color;// 上下左右四个⽅向 for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){q.add(new int[]{x, y});}}}return image;}}

题目二： 岛屿数量

1. 题⽬链接：

https://leetcode.cn/problems/number-of-islands/description/

2. 题⽬描述：

给你⼀个由 ‘1’（陆地）和 ‘0’（⽔）组成的的⼆维⽹格，请你计算⽹格中岛屿的数量。
岛屿总是被⽔包围，并且每座岛屿只能由⽔平⽅向和/或竖直⽅向上相邻的陆地连接形成。 此外，你可以假设该⽹格的四条边均被⽔包围。

3. 算法思路：

遍历整个矩阵，每次找到**「⼀块陆地」**的时候：

• 说明找到**「⼀个岛屿」**，记录到最终结果 ret ⾥⾯；

•
并且将这个陆地相连的所有陆地，也就是这块「岛屿」，全部「变成海洋」。这样的话，我们下次遍历到这块岛屿的时候，它「已经是海洋」了，不会影响最终结果。

• 其中「变成海洋」的操作，可以利⽤「深搜」和「宽搜」解决，其实就是上一题 图像渲染 这道题~ 这样，当我们，遍历完全部的矩阵的时候，
ret 存的就是最终结果。

4.代码

在这里class Solution 
{int[] dx = {0, 0, -1, 1};int[] dy = {1, -1, 0, 0};boolean[][] vis = new boolean[301][301];int m, n;public int numIslands(char[][] grid) {m = grid.length; n = grid[0].length;int ret = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1' && !vis[i][j]){ret++;bfs(grid, i, j);}}}return ret;}public void bfs(char[][] grid, int i, int j){Queue<int[]> q = new LinkedList<>();q.add(new int[]{i, j});vis[i][j] = true;while(!q.isEmpty()){int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && 
!vis[x][y]){q.add(new int[]{x, y});vis[x][y] = true;}}}}
}插入代码片

题目三：被围绕的区域

1. 题⽬链接：

https://leetcode.cn/problems/surrounded-regions/description/

2. 题⽬描述：

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

提示：

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

3. 算法思路：

算法思路：
正难则反。 可以先利⽤ bfs 将与边缘相连的 ‘0’ 区域做上标记，然后重新遍历矩阵，将没有标记过的 ‘0’

修改成 ‘X’ 即可。

4.代码

class Solution 
{int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m, n;public void solve(char[][] board) {m = board.length; n = board[0].length;// 1. 先处理边界的 'O' 联通块，全部修改成 '.' for(int j = 0; j < n; j++){if(board[0][j] == 'O') bfs(board, 0, j);if(board[m - 1][j] == 'O') bfs(board, m - 1, j);}for(int i = 0; i < m; i++){if(board[i][0] == 'O') bfs(board, i, 0);if(board[i][n - 1] == 'O') bfs(board, i, n - 1);}// 2. 还原 for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(board[i][j] == 'O') board[i][j] = 'X';else if(board[i][j] == '.') board[i][j] = 'O';}public void bfs(char[][] board, int i, int j){Queue<int[]> q = new LinkedList<>();q.add(new int[]{i, j});board[i][j] = '.';while(!q.isEmpty()){int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){board[x][y] = '.';q.add(new int[]{x, y});}}}}
}