733. Flood Fill — Easy

前往題目

想法

• 這題之前做過，第一直覺是用BFS，寫到queue就卡住了，時間用得有點多，直接看答案

思路

1. 檢查初始cell的顏色是否和要填充的顏色一樣
2. 在每個cell確認沒有出界、和初始cell顏色一樣，就可以被填充
3. 檢查及填充每個cell的上下左右的cell

Code

實際上是DFS

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int initColor = image[sr][sc];

        // Base case
        if (image[sr][sc] == color) {
            return image;
        }

        // Fill the image
        fill(image, sr, sc, initColor, color);
        return image;
    }

    private void fill(int[][] image, int r, int c, int initColor, int color) {
        // Check in bound
        if (!inBound(r, c, image)) return;
        
        // Check if the same with initial color
        if (image[r][c] != initColor) return;

        // Fill the color
        image[r][c] = color;

        // Fill the rest possible cells
        fill(image, r + 1, c, initColor, color);
        fill(image, r - 1, c, initColor, color);
        fill(image, r, c + 1, initColor, color);
        fill(image, r, c - 1, initColor, color);
    }

    // Inside the boundary
    private boolean inBound(int r, int c, int[][] image) {
        return r >= 0 && r < image.length
                && c >= 0 && c < image[0].length;
    }
}

2023/12/02再次嘗試

• 這次自己20分鐘寫出來了，用的還是之前卡住的BFS

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        // Base case
        if (image[sr][sc] == color) return image;

        final int M = image.length;
        final int N = image[0].length;
        int sourceColor = image[sr][sc];
        Queue<int[]> q = new LinkedList<>();

        // 4 dimension
        int[][] dims = new int[][]{
            {1, 0}, // up
            {-1, 0}, // down
            {0, -1}, // left
            {0, 1}, // right
        };

        // Add the source
        q.offer(new int[]{sr, sc});
        // Change the color of the source cell
        image[sr][sc] = color;
        
        // BFS
        while (!q.isEmpty()) {
            int[] cell = q.poll();

            // Check every dimension
            for (int[] dim : dims) {
                // Checking neighbours
                int row = dim[0] + cell[0];
                int col = dim[1] + cell[1];

                if (inBound(M, N, row, col) && 
                    image[row][col] == sourceColor) {
                    // Change the color
                    image[row][col] = color;
                    // Add to the queue
                    q.offer(new int[]{row, col});
                }
            }
        }
        return image;
    }

    private boolean inBound(int M, int N, int row, int col) {
        return row >= 0 && row < M && col >= 0 && col < N;
    }
}