DFS、BFS求解leetcode图像渲染问题(Java)
2023-12-13 21:53:04
目录
leetcode733题.图像渲染
有一幅以?
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.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], newColor < 216
0 <= sr <?m
0 <= 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作为条件,以确保正确地访问数组中的元素。
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
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;
}
}
//来个没那么多注释的 显得整洁
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;
}
}
文章来源:https://blog.csdn.net/xiaoliii0401/article/details/134911051
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!