目录
leetcode733%E9%A2%98.%E5%9B%BE%E5%83%8F%E6%B8%B2%E6%9F%93-toc" style="margin-left:0px;">leetcode733题.图像渲染
DFS
BFS
leetcode733%E9%A2%98.%E5%9B%BE%E5%83%8F%E6%B8%B2%E6%9F%93">leetcode733题.图像渲染
733. 图像渲染 - 力扣（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]]提示:
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], newColor < 2160 <= sr < m0 <= sc < n
题目解析：一个矩阵，大小是M*N ，在[sr][sc]处涂色，（sr即row，横坐标 ；sc即column，纵坐标）但是要涂的颜色不能和他本来的颜色一样 ，如果在一个元素的前后左右跟他颜色是一样的话，那可以被涂上新颜色。
DFS
- 创建一个与图像大小相同的布尔数组，用于标记已经访问过的像素。
- 调用dfs方法进行深度优先搜索，将起始点的像素颜色替换为目标颜色，并标记为已访问。
- 在dfs方法中，递归地对起始点的上下左右四个方向进行搜索，将与起始点颜色相同且未访问过的像素替换为目标颜色，并标记为已访问。
- 最终返回填充后的图像数组。
- 在给定的解决方案中，val代表的是起始点(sr, sc)的原始颜色值。在深度优先搜索的过程中，会检查当前像素的颜色是否与val相同，如果相同则将其替换为目标颜色color。val的作用是用来判断当前像素的颜色是否与起始点的颜色相同，从而进行相应的填充操作。
-
在给定的代码中，判断条件是i >= 0和j >= 0，而不是i > 0和j > 0的原因是因为数组的索引是从0开始的。在Java中，数组的索引从0开始，因此当i和j等于0时，表示数组的第一个元素。因此，为了确保不越界，需要使用i >= 0和j >= 0作为条件，以防止访问数组的负索引。如果使用i > 0和j > 0作为条件，那么在i或j等于0时，就会跳过数组的第一行或第一列，这显然是不正确的。因此，应该使用i >= 0和j >= 0作为条件，以确保正确地访问数组中的元素。
java">class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int m = image.length;
int n = image[0].length;
boolean[][] booleans = new boolean[m][n];
dfs(image,booleans,sr,sc,color,image[sr][sc]);
return image;
}
public void dfs(int[][] image,boolean[][] booleans,int i,int j,int color,int val){
if (i >= 0 && j >= 0 && i < image.length && j< image[0].length&& !booleans[i][j] && image[i][j] == val) {
booleans[i][j] = true;
image[i][j] = color;
dfs(image,booleans,i+1,j,color,val);
dfs(image,booleans,i-1,j,color,val);
dfs(image,booleans,i,j+1,color,val);
dfs(image,booleans,i,j-1,color,val);
}
}
}
BFS
java">
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
//以这个元素为中心 把符合要求的上下左右元素的 “坐标” 塞到队列里 同时把他现在的颜色记录下来
//被涂过颜色的变成color了 没被涂过颜色的之前已经被记录下来了
if(image==null || image.length==0 || image[0].length==0 || image[sr][sc]==color)
//如果 二维数组是不存在的 || 二维数组的深度↓是0 || 二维数组的宽度→是0 || 要涂的元素正好是新颜色
{
return image;//那就不做
}
int m= image.length-1;//获取整个二维数组的最深下标↓
//二维数组.length -> 有多少个一维数组 也就是深度
int n= image[0].length-1;//获取整个二维数组的最远下标→
//二维数组[0].length -> 每个一维数组的长度是多少
int oldcolor = image[sr][sc];//先把当前的颜色记住 这个是原来的颜色
Queue<int []> queue = new LinkedList();//先整一个队列 这个队列里面放的是符合条件的元素的“坐标”
queue.offer(new int[] {sr,sc} );//把一开始要我们涂的元素的坐标记录下来 塞到队列里去
while(!queue.isEmpty())//如果队列不空 也就是还有元素要被涂色
{
int point []= queue.poll();//让元素出队 获取元素的坐标
//{i,j} i是这个元素的横坐标 j是纵坐标
int i = point[0];//获取横坐标
int j = point[1];//获取纵坐标
//i是管上下的 j是管左右的
image[i][j]=color;//给元素上色
//这个点的上下左右找
//最左边的下标就是0 最右边的下标就是n
//最上边的下标就是0 最下边的下标就是m
if(i-1>=0 && image[i-1][j]==oldcolor)//如果向下移动不越界 且 他左边的元素没有被涂过色
{
queue.offer(new int[]{i-1,j});//那么就把他下边的元素的“坐标”记录下来 入队
}
if(i+1<=m && image[i+1][j]==oldcolor)//如果向上移动不越界 且 他右边的元素没有被涂过色
{
queue.offer(new int[]{i+1,j});//那么就把他上边的元素的“坐标”记录下来 入队
}
if(j-1>=0 && image[i][j-1]==oldcolor)//如果向左移动不越界 且 他上边的元素没有被涂过色
{
queue.offer(new int[]{i,j-1});//那么就把他左边的元素的“坐标”记录下来 入队
}
if(j+1<=n && image[i][j+1]==oldcolor)//如果向右移动不越界 且 他下边的元素没有被涂过色
{
queue.offer(new int[]{i,j+1});//那么就把他右边的元素的“坐标”记录下来 入队
}
}
//做完了就返回该二维数组
return image;
}
}
java">//来个没那么多注释的 显得整洁
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
if(image==null || image.length==0 || image[0].length==0 || image[sr][sc]==color)
{
return image;
}
int m= image.length-1;
int n= image[0].length-1;
int oldcolor = image[sr][sc];
Queue<int []> queue = new LinkedList();//这个队列里面放的是符合条件的元素的坐标
queue.offer(new int[] {sr,sc} );
while(!queue.isEmpty())//如果队列不空 也就是还有元素要被涂色
{
int point []= queue.poll();
int i = point[0];//获取横坐标
int j = point[1];//获取纵坐标
//i是管上下的 j是管左右的
image[i][j]=color;//给元素上色
//最左边的下标就是0 最右边的下标就是n
//最上边的下标就是0 最下边的下标就是m
if(i-1>=0 && image[i-1][j]==oldcolor)
{
queue.offer(new int[]{i-1,j});
}
if(i+1<=m && image[i+1][j]==oldcolor)
{
queue.offer(new int[]{i+1,j});
}
if(j-1>=0 && image[i][j-1]==oldcolor)
{
queue.offer(new int[]{i,j-1});
}
if(j+1<=n && image[i][j+1]==oldcolor)
{
queue.offer(new int[]{i,j+1});
}
}
return image;
}
}
