LeetCode 75 Level 1 - Day 9 Graph/BFS/DFS

733. Flood Fill

• 題目連結
• 難易度：Easy

題目敘述

An image is represented by an m x n integer grid image where image[ i ][ j ] represents the pixel value of the image.
You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[ sr ][ sc ].
To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.
Return the modified image after performing the flood fill.

預設函數

/**
 * 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 color, int* returnSize, int** returnColumnSizes){

}

題目限制

• m == image.length
• n == image[ i ].length
• 1 <= m, n <= 50
• 0 <= image[ i ][ j ], color <
• 0 <= sr < m
• 0 <= sc < n

解題過程及程式碼

今天進入了新主題Graph/BFS/DFS，題目給一個二維陣列，內部資料是整數所代表的各種顏色，再給一個整數表示一個要改變成的目標顏色，接著給一個二維陣列內部的起始座標，目標就是將起始座標的顏色換成目標顏色 (如果要改的被改的兩者一樣就不用換)，換顏色過程是會向上、下、左、右擴散的，只要起始座標上下左右有和起始座標相同的顏色就會被換成目標顏色，直到全部擴散完，最後將改變完的陣列回傳。

如下圖所示 (來源: Leetcode)

• 一個3x3的二維陣列
• 起始座標是 (1, 1)，它的顏色是 1。
• 目標顏色是 2
  擴散的過程就是從 (1, 1)出發，上下左右看看 (0, 1)和 (1, 0)被染成2了，從(0, 1)出發 (0, 0)和 (0, 2)都變2，最後從 (1, 0)出發 (2, 0)也變2。

想法是利用程式遞迴，檢查首先檢查起始座標是不是要改變的顏色，接著改變顏色，再依序確認右方、上方、左方、下方位置是否超出範圍，若範圍合理則代入新位置再呼叫函數 (記得確認新位置是否超過邊界)

• 程式碼上傳

#define ROW 50
#define COL 50

int color1, color2;
int a_limit, b_limit;

int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int color, int* returnSize, int** returnColumnSizes){
    int **dynArr2D = (int **)malloc(sizeof(int *) * ROW);

    for (int i=0; i<ROW; i++) {
        dynArr2D[i] = (int *)malloc(sizeof(int) * COL);
    }

    color1 = image[sr][sc];
    color2 = color;

    a_limit = imageSize;
    b_limit = imageColSize[0];

    for (int i=0; i<a_limit; i++) {
        for (int j=0; j<b_limit; j++) {
            dynArr2D[i][j] = image[i][j];
        }
    }

    if (color1 != color2) {
        do_fill(sr, sc, dynArr2D);
    }

    *returnColumnSizes = imageColSize;
    *returnSize = imageSize;
    return dynArr2D;
}

void do_fill(int a, int b, int **img) {
    if (img[a][b] != color1) {
        return;
    }
    img[a][b] = color2;

    if (check_b_range(b + 1)) {                /* 向右塗滿 */
        do_fill(a, b + 1, img);
    }

    if (check_a_range(a - 1)) {               /* 向上塗滿 */
        do_fill(a - 1, b, img);
    }

    if (check_b_range(b - 1) == 1) {          /* 向左塗滿 */
        do_fill(a, b - 1, img);
    }

    if (check_a_range(a + 1)) {               /* 向下塗滿 */
        do_fill(a + 1, b, img);
    }
}

/* 確認新位置是否超出邊界 */
int check_a_range(int a) {
    if ((a < a_limit) && (a >= 0)) {
        return 1;
    } else {
        return 0;
    }
}

int check_b_range(int b) {
    if ((b < b_limit) && (b >= 0)) {
        return 1;
    } else {
        return 0;
    }
}

今天到這裡，謝謝大家!