【DFS】733. 图像渲染

小鱼儿 2022-11-28 00:41 126阅读 0赞

# 1. 题目描述 #

## [【DFS】图像渲染][DFS] ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]

# 2. 题目分析 #

1.  题目给你了一个二维的地图，给你一个出发点的坐标，基本很明确了，就是考察的图的DFS或BFS
2.  这里，题主选择的是DFS的非递归版本（不要问我为啥不用递归版本，因为我脑子理解不了递归~ \_ ~），不过非递归也有一个好处，就是一些边界、满足条件，容易写和容易理解。
3.  简单说一下思路，从坐标点出发，遍历上下左右4个点，遇到符合的（和坐标点相等），直接入栈，并标记一下该点，并将该点的值变成newColor,

# 3. 题目代码 #

class Solution {
        
      public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        
    		int[][] vis = new int[image.length][image[0].length];
            if(newColor == image[sr][sc]){
        
                return image;
            }
    		DFS(image, sr, sc, vis, newColor);
    		return image;
    	}
    
    	public static void DFS(int[][] image, int sr, int sc, int[][] vis, int newColor) {
        
    		int xMax = image.length;
    		int yMax = image[0].length;
    		int d = image[sr][sc];
    		Stack<Integer> stack1 = new Stack<Integer>();
    		Stack<Integer> stack2 = new Stack<Integer>();
    		stack1.add(sr);
    		stack2.add(sc);
    		vis[sr][sc] = 1;
            image[sr][sc] = newColor;
    		while (!stack1.isEmpty() && !stack2.isEmpty()) {
        
    			int x = stack1.pop();
    			int y = stack2.pop();
    			if (x - 1 >= 0 && image[x - 1][y] == d && vis[x - 1][y] == 0) {
        
    				stack1.add(x - 1);
    				stack2.add(y);
    				vis[x - 1][y] = 1;
                    image[x-1][y] = newColor;
    			}
    			if (x + 1 < xMax && image[x + 1][y] == d && vis[x + 1][y] == 0) {
        
    				stack1.add(x + 1);
    				stack2.add(y);
    				vis[x + 1][y] = 1;
                    image[x+1][y] = newColor;
    			}
    			if (y - 1 >= 0 && image[x][y - 1] == d && vis[x][y - 1] == 0) {
        
    				stack1.add(x);
    				stack2.add(y - 1);
    				vis[x][y - 1] = 1;
                    image[x][y-1] = newColor;
    			}
    			if (y + 1 < yMax && image[x][y + 1] == d && vis[x][y + 1] == 0) {
        
    				stack1.add(x);
    				stack2.add(y + 1);
    				vis[x][y + 1] = 1;
                    image[x][y+1] = newColor;
    			}
    		}
    	}
    }

[DFS]: https://leetcode-cn.com/problems/flood-fill/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/9e08c43a1ad64f69a0d4bc57b21346ee.png