图像渲染【leetcode - 733 - 简单】

朴灿烈づ我的快乐病毒、 2022-03-30 03:11 193阅读 0赞

胡扯：这个题在评论区有人说看不懂，我个人觉得还比较好理解。建议遇到不太好理解的题目的时候，动手拿笔写写画画，有助于理解。日常吐槽 leetcode 不可以用全局变量的问题。明明说是 c/c++，不可以，但是我用的是java啊。

题目地址 ：[https://leetcode-cn.com/problems/flood-fill/][https_leetcode-cn.com_problems_flood-fill]

还有个问题，就是有时候那个执行时间不必去在意。当然很大程度是你的算法不够好。但我今天同样的代码，提交多次，出现了相差十几秒的情况。

## 思路： ##

1、在每一个位置进行前后左右的移动。这个题移动的时候需要判断一下，当下一个点不具备 改变的可能的时候，也就是不等于最开始位置的值，我们不需要对它进行递归。

2、在每一个位置我们是否需要对它进行重新赋值的标准是，它的上下左右是否有 newColor，所以对于每一个可能 赋值 的位置，我们都需要进行一个判断。

3、我们优先处理当数组为空的时候，直接返回该数组。

4、我们在主方法里面，要进行处理把起始位置，进行开始的赋值。 不然进入递归的时候，可能出现它的上下左右没有newColor ，但是很明显起始位置不需要进行这样的判断。

5、我们需要对每一个位置进行存储起来，表示我们是否已经走过该路线，用 set 很合适。

代码

class Solution {
        
        
        int[][] move = {
       {0,-1},{0,1},{-1,0},{1,0}};     //上下左右移动
        public void dfs(int[][] arr, int r, int c,int ini,int newColor,Set<String> set){
            
            //判断当前 的点是否需要变色
            for (int i = 0;i < 4; i++){
                int newr = r + move[i][0];
                int newc = c + move[i][1];
                if (newr >= 0 && newc >= 0 && newr < arr.length && newc < arr[0].length){
                    if(arr[newr][newc] == newColor){
                        arr[r][c] = newColor;
                        break;
                    }
                }
            }
            
            //递归的去判断下面那些点可能变色
            for (int i = 0;i < 4; i++){
                int newr = r + move[i][0];
                int newc = c + move[i][1];
                if (newr >= 0 && newc >= 0 && newr < arr.length && newc < arr[0].length){
                    if ( set.contains(""+newr+newc) )
                        continue;
                    set.add(""+newr+newc);
                    if (arr[newr][newc] == ini)
                        dfs(arr,newr,newc,ini,newColor,set);
                }
            }
        }
        
        public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
            
            if(image.length == 0 && image[0].length == 0)
                return image;
    
            Set<String> set = new HashSet<>();      //用来存放走过的路线
            int ini = image[sr][sc];                //最开始的数值
            image[sr][sc] = newColor;               
            set.add(""+sr+sc);
            dfs(image,sr,sc,ini,newColor,set);
            return image;
        }
    }

[https_leetcode-cn.com_problems_flood-fill]: https://leetcode-cn.com/problems/flood-fill/