leetcode-面试题 08.10. 颜色填充

原始思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int n1 = image.length;
        int n2 = image[0].length;
        int[][] visit = new int[n1][n2];
        int origin = image[sr][sc];
        dfs(image, sr, sc, newColor, n1, n2, visit, origin);
        return image;
    }

    public void dfs(int[][] image, int sr, int sc, int newColor, int n1, int n2, int[][] visit, int origin) {
        // 判断边界条件
        if (sr < 0 || sr >= n1 || sc < 0 || sc >= n2) {
            return;
        }

        // 为0证明不通了
        if (image[sr][sc] != origin) {
            return;
        }

        //如果是已经访问过的,则直接返回
        if (visit[sr][sc] == 1) {
            return;
        }

        // 更改颜色
        image[sr][sc] = newColor;

        // 记录该位置是否被访问过
        visit[sr][sc] = 1;

        dfs(image, sr - 1, sc, newColor, n1, n2, visit, origin);
        dfs(image, sr + 1, sc, newColor, n1, n2, visit, origin);
        dfs(image, sr, sc - 1, newColor, n1, n2, visit, origin);
        dfs(image, sr, sc + 1, newColor, n1, n2, visit, origin);
    }
}