图像渲染(Flood Fill)

有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一个新的颜色值 newColor,让你重新上色这幅图像。

为了完成上色工作,从初始坐标开始,记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点,接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点,……,重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

输入: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 
在图像的正中间,(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意,右下角的像素没有更改为2,
因为它不是在上下左右四个方向上与初始点相连的像素点。

注意:

  • imageimage[0] 的长度在范围 [1, 50] 内。
  • 给出的初始点将满足 0 <= sr < image.length0 <= sc < image[0].length
  • image[i][j]newColor 表示的颜色值在范围 [0, 65535]内。
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** floodFill(
        int** image,
        int imageSize,
        int* imageColSize,
        int sr, int sc,
        int newColor,
        int* returnSize,
        int** returnColumnSizes){
    const int nRows = imageSize;
    const int nCols = imageColSize[0];
    *returnSize = nRows;
    *returnColumnSizes = malloc(sizeof(int)*nCols);
    for (int i = 0; i < nCols; ++i) {
        (*returnColumnSizes)[i] = nCols;
    }

    int** result = malloc(sizeof(int*)*nRows);
    for (int row = 0; row < nRows; ++row) {
        result[row] = malloc(sizeof(int)*nCols);
    }
    for (int row = 0; row < nRows; ++row) {
        for (int col = 0; col < nCols; ++col) {
            result[row][col] = image[row][col];
        }
    }

    int target = image[sr][sc];
    result[sr][sc] = -1;
    bool isFound = true;
    while (isFound){
        isFound = false;
        for (int row = 0; row < nRows; ++row) {
            for (int col = 0; col < nCols; ++col) {
                // up
                if (result[row][col] == -1 && row>0 && result[row-1][col] == target){
                    result[row-1][col] = -1;
                    isFound = true;
                }
                // down
                if (result[row][col] == -1 && row+1<nRows && result[row+1][col] == target){
                    result[row+1][col] = -1;
                    isFound = true;
                }
                // left
                if (result[row][col] == -1 && col>0 && result[row][col-1] == target){
                    result[row][col-1] = -1;
                    isFound = true;
                }
                // right
                if (result[row][col] == -1 && col+1<nCols && result[row][col+1] == target){
                    result[row][col+1] = -1;
                    isFound = true;
                }
            }
        }
    }
    for (int row = 0; row < nRows; ++row) {
        for (int col = 0; col < nCols; ++col) {
            if (result[row][col] == -1){
                result[row][col] = newColor;
            }
        }
    }
    return result;
}

最简单粗暴的做法,这样的时间复杂度是比较难以估计的

void rFloodFill(int** result,
                int row,
                int col,
                int target,
                int nRows,
                int nCols){
    if (row>0 && result[row-1][col] == target){
        result[row-1][col] = -1;
        rFloodFill(result, row-1, col, target, nRows, nCols);

    }
    // down
    if (row+1<nRows && result[row+1][col] == target){
        result[row+1][col] = -1;
        rFloodFill(result, row+1, col, target, nRows, nCols);
    }
    // left
    if (col>0 && result[row][col-1] == target){
        result[row][col-1] = -1;
        rFloodFill(result, row, col-1, target, nRows, nCols);
    }
    // right
    if (col+1<nCols && result[row][col+1] == target){
        result[row][col+1] = -1;
        rFloodFill(result, row, col+1, target, nRows, nCols);
    }
}

int** floodFill(
        int** image,
        int imageSize,
        int* imageColSize,
        int sr, int sc,
        int newColor,
        int* returnSize,
        int** returnColumnSizes){
    const int nRows = imageSize;
    const int nCols = imageColSize[0];
    *returnSize = nRows;
    *returnColumnSizes = malloc(sizeof(int)*nCols);
    for (int i = 0; i < nCols; ++i) {
        (*returnColumnSizes)[i] = nCols;
    }

    int** result = malloc(sizeof(int*)*nRows);
    for (int row = 0; row < nRows; ++row) {
        result[row] = malloc(sizeof(int)*nCols);
    }
    for (int row = 0; row < nRows; ++row) {
        for (int col = 0; col < nCols; ++col) {
            result[row][col] = image[row][col];
        }
    }

    int target = image[sr][sc];
    result[sr][sc] = -1;

    rFloodFill(result, sr, sc, target, nRows, nCols);

    for (int row = 0; row < nRows; ++row) {
        for (int col = 0; col < nCols; ++col) {
            if (result[row][col] == -1){
                result[row][col] = newColor;
            }
        }
    }
    return result;
}

更精简版本

void rFloodFill(int** result,
                int row,
                int col,
                int target,
                int nRows,
                int nCols){
    if (row<0 || row>= nRows || col<0 || col>=nCols) return;
    if (result[row][col] != target) return;
    result[row][col] = -1;
    rFloodFill(result, row-1, col, target, nRows, nCols);
    rFloodFill(result, row+1, col, target, nRows, nCols);
    rFloodFill(result, row, col-1, target, nRows, nCols);
    rFloodFill(result, row, col+1, target, nRows, nCols);
}

int** floodFill(
        int** image,
        int imageSize,
        int* imageColSize,
        int sr, int sc,
        int newColor,
        int* returnSize,
        int** returnColumnSizes){
    const int nRows = imageSize;
    const int nCols = imageColSize[0];
    *returnSize = nRows;
    *returnColumnSizes = malloc(sizeof(int*)*nCols);
    for (int i = 0; i < nCols; ++i) {
        (*returnColumnSizes)[i] = nCols;
    }

    int** result = malloc(sizeof(int*)*nRows);
    for (int row = 0; row < nRows; ++row) {
        result[row] = malloc(sizeof(int)*nCols);
    }
    for (int row = 0; row < nRows; ++row) {
        for (int col = 0; col < nCols; ++col) {
            result[row][col] = image[row][col];
        }
    }

    int target = image[sr][sc];

    rFloodFill(result, sr, sc, target, nRows, nCols);

    for (int row = 0; row < nRows; ++row) {
        for (int col = 0; col < nCols; ++col) {
            if (result[row][col] == -1){
                result[row][col] = newColor;
            }
        }
    }
    return result;
}

找bug真的火葬场