Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Brush addiction plan

takeaway

Projects that have been implemented (and can be found on my blog) :

Since I began to record my brush notes from daily fertilizer series, to dynamic planning 21 days, and then to dachang special training 28 days, and do not attack the DFS do not match series. You can go and have a look. From the final result, I received some like-minded friends to brush the questions together. If you also want to join us, we can directly send a message to me to join us, or you can leave a message below to punch in. Now our team is not very big, but there are some successful students, some have entered good companies (of course, not all by brushing questions) and some have got the competition certificate. I’m going to keep going, and we’re going to cultivate this addiction. So let’s do another 28-day addiction training program. We’ll sum it up when the 28 days are over.

PS: The algorithm is not very different language everyone can come.

The title

There is a picture image represented by a two-dimensional integer array of M x n, where image[I][j] represents the pixel value of the picture.

You are also given three integers SR, SC and newColor. You should start filling the image with pixel image[SR][SC].

In order to complete the coloring work, starting from the initial pixel, record the connected pixels with the same pixel value in the four directions of the initial coordinate, and then record the qualified pixels in these four directions and their corresponding connected pixels with the same pixel value in the four directions of the initial coordinate… And repeat the process. Change the color value of all recorded pixels to newColor.

Finally, the color rendered image is returned.

Example 1:

Input: image = [,1,1 [1], [1, 0], [1, 1]], the sr = 1, sc = 1, newColor = 2 output: [,2,2 [2], [2 0], [2, 1]] resolution: In the middle of the image, (coordinates (sr,sc)=(1,1)), the color of all eligible pixels on the path is changed to 2. Notice that the lower-right pixel is not changed to 2 because it is not the pixel that is connected to the initial point in four directions: up, down, left, and right.Copy the code

Example 2: input: image = [[0, 0], [0, 0]], the sr = 0, sc = 0, newColor = 2 output: [,2,2 [2], [2,2,2]]Copy the code

Test address: address

We start with a given starting point and do a depth-first search. Every time a square is searched, if it has the same color as the square in the initial position, the color of the square is updated to prevent repeated searches; If not, backtrack.

Note: Since the color of the initial position will be changed, we need to save the color of the initial position for later update operations.

Solution a:

class Solution {
    int[] x={0.0, -1.1};// up, down, left and right
    int[] y={1, -1.0.0};
    public int[][] dfs(int[][]image,int sr,int sc,int newColor,int flag){
        if((image[sr][sc]! =flag)||(newColor==flag))return image;
        image[sr][sc]=newColor;
        for(int i=0; i<4; i++){int row=x[i]+sr;
            int col=y[i]+sc;
            if(row<=image.length-1&&row>=0&&col>=0&&col<=image[0].length-1) {// Determine whether overflow occurs
                dfs(image,row,col,newColor,flag);
                 if(image[row][col]==flag){ image[row][col]=newColor; }}}return image;
    }
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int flag=image[sr][sc];
        returndfs(image,sr,sc,newColor,flag); }}Copy the code

Solution 2:

class Solution {
    int[] dx = {1.0.0, -1};
    int[] dy = {0.1, -1.0};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];
        if(currColor ! = newColor) { dfs(image, sr, sc, currColor, newColor); }return image;
    }

    public void dfs(int[][] image, int x, int y, int color, int newColor) {
        if (image[x][y] == color) {
            image[x][y] = newColor;
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length) {
                    dfs(image, mx, my, color, newColor);
                }
            }
        }
    }
}


Copy the code

debugging

Here is the debugging code: you can debug in Eclipse or IDEA

public class Solution {

	int[] x = { 0.0, -1.1 };// up, down, left and right
	int[] y = { 1, -1.0.0 };

	public int[][] dfs(int[][] image, int sr, int sc, int newColor, int flag) {
		if((image[sr][sc] ! = flag)||(newColor==flag))return image;
		image[sr][sc] = newColor;
		for (int i = 0; i < 4; i++) {
			int row = x[i] + sr;
			int col = y[i] + sc;
			if (row <= image.length - 1 && row >= 0 && col >= 0 && col <= image[0].length - 1) {
				dfs(image, row, col, newColor, flag);
				if(image[row][col] == flag) { image[row][col] = newColor; }}}return image;
	}

	public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
		int flag = image[sr][sc];
		return dfs(image, sr, sc, newColor, flag);

	}

	public static void main(String[] args) {
		Solution s=new Solution();
		int[][] image= {{0.0.0}, {0.1.1}};
		image=s.floodFill( image, 1.1.1);
		for(int[] i:image) {
			for(int j:i) {
				System.out.print(j+""); } System.out.println(); }}}Copy the code

Important things

Let me know if you have any problems learning Python or Java or even C, because beginners are always going to make a lot of mistakes and it’s easy to give up without someone to help you. There are many such examples around. Many people change their major and direction after learning. It is not only their own problems or the correct learning. So, as someone who’s been there before, I’d like to leave a message if you have any questions, either to help or to type a few lines.