Problem: 面试题 08.10. 颜色填充

题目描述

思路

该问题可以归纳为一类遍历二维矩阵的题目，此类中的一部分题目可以利用DFS来解决，具体到本题目：

1.我们从题目给定点处开始依次以上下左右的顺序依次判断是否DFS，具体到代码实现中，我们可以用一个二维数组int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};记录每一个点的四个方位，在开始遍历同时判断；
2.我们在循环中每次得到一个新的点的横纵坐标并判断其是否合法，具体到代码中我们要求新得到的横纵坐标不超过给定二维数组的索引范围，同时新坐标的值不等给定位置的值、新坐标的值等于给定待修改的值（newCol）

解题方法

1.调用dfs函数，返回image
2.dfs函数：

2.1 每次将当前得到的合法位置修改成给定的值（newCol）
2.2 用一个二维数组int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};记录每一个点的四个方位
2.3 for循环开始查找遍历（循环范围1-4），每次得到一个新的坐标（int newI = sr + directions[i][0];int newJ = sc + directions[i][1];）
2.4 每次对新的坐标判断，若新得到的横纵坐标不超过给定二维数组的索引范围，同时新坐标的值不等给定位置的值、新坐标的值等于给定待修改的值（newCol）则DFS，否则继续循环查找下一个合法的位置

复杂度

时间复杂度:

$O(mn)$

空间复杂度:

$O(mn)$

Code

java">class Solution {
    /**
     * Sets all numbers of the location connected to the specified location to the given number
     *
     * @param image    Given two-dimensional array
     * @param sr       The abscissa of a given position
     * @param sc       The ordinate of a given position
     * @param newColor Given number
     * @return int[][]
     */
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int row = image.length;
        int col = image[0].length;
        dfs(image, row, col, sr, sc, image[sr][sc], newColor);
        return image;
    }

    /**
     * Sets all numbers of a location connected to a specified location to a given number by DFS
     *
     * @param image    Given two-dimensional array
     * @param row      The number of rows of a given matrix
     * @param col      The number of columns  of a given matrix
     * @param sr       The abscissa of a given position
     * @param sc       The ordinate of a given position
     * @param color    The value of the original given position
     * @param newColor Given number
     */
    private void dfs(int[][] image, int row, int col, int sr, int sc, int color, int newColor) {
        //Change the current position to newColor
        image[sr][sc] = newColor;
        //Recode the directions
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < 4; ++i) {
            int newI = sr + directions[i][0];
            int newJ = sc + directions[i][1];
            if (newI < 0 || newI >= row || newJ < 0 || newJ >= col
                    || image[newI][newJ] != color || image[newI][newJ] == newColor) {
                continue;
            }
            dfs(image, row, col, newI, newJ, color, newColor);
        }
    }
}