0733 - Flood Fill (Easy)

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
Output: [[2,2,2],[2,2,2]]

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        R, C = len(image), len(image[0])
        color = image[sr][sc]
        # check if the color is same as the target one
        # if so, return input directly
        if color == newColor: return image
        # dfs function
        def dfs(r, c):
            # check if it is same as the original color
            if image[r][c] == color:
                # paint it
                image[r][c] = newColor
                # check 4 directions
                # perform dfs only if the next pixel is within boundary
                if r > 0: dfs(r - 1, c)
                if r < R - 1: dfs(r + 1, c)
                if c > 0: dfs(r, c - 1)
                if c < C - 1: dfs(r, c + 1)
        # perform flood fill from the starting point
        dfs(sr, sc)
        return image

class Solution {

    public final int NO_DIRS = 4;
    public int[] DIRS = {0, 1, 0, -1, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image[sr][sc] == color) return image;
        Set<String> visited = new HashSet<>();
        fill(image, sr, sc, image[sr][sc], color, visited);
        return image;
    }

    public void fill(int[][] image, int sr, int sc, int color, int newColor, Set<String> visited) {
        boolean rowInbounds = (0 <= sr && sr < image.length);
        boolean colInbounds = (0 <= sc && sc < image[0].length);
        // Check row and column bounds
        if (!rowInbounds || !colInbounds) return;
        // If color is not same as existing then skip
        if (image[sr][sc] != color) return;
        // Change the color
        image[sr][sc] = newColor;
        String key = sr + "#" + sc;
        // Mark as visited, so that the same row and column won't be repeated
        visited.add(key);
        for (int idx = 0; idx < NO_DIRS; idx++) {
            key = sr + DIRS[idx] + "#" + sc + DIRS[idx + 1];
            if (!visited.contains(key)) {
                fill(image, sr + DIRS[idx], sc + DIRS[idx + 1], color, newColor, visited);
            }
        }
    }
}

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} color
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, color) {
  if (image == null || image[sr][sc] == color) return image;
  dfs(image, sr, sc, image[sr][sc], color);
  return image;

  function dfs(image, r, c, initial, color) {
    if (
      r < 0 ||
      r >= image.length ||
      c < 0 ||
      c >= image[0].length ||
      image[r][c] != initial
    ) {
      return;
    }
    image[r][c] = color;
    dfs(image, r + 1, c, initial, color);
    dfs(image, r - 1, c, initial, color);
    dfs(image, r, c + 1, initial, color);
    dfs(image, r, c - 1, initial, color);
  }
};

class Solution {
public:
    int dirx[4] = { -1, 0, 0, 1};
    int diry[4] = { 0, 1, -1, 0};

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int oriColor = image[sr][sc];
        if (oriColor == newColor) return image;
        int n = image.size(), m = image[0].size();
        queue<pair<int, int>> q;
        q.push({sr, sc});
        while(!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            image[x][y] = newColor;
            for(int i = 0; i < 4; i++) {
                int next_x = x + dirx[i];
                int next_y = y + diry[i];
                if(next_x < 0 || next_y < 0 || next_x > n - 1 || next_y > m - 1 || image[next_x][next_y] != oriColor) continue;
                image[next_x][next_y] = newColor;
                q.push({next_x, next_y});
            }
        }
        return image;
    }
};

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        queue = deque([(sr, sc)])
        visited = set([(sr, sc)])
        n,m = len(image), len(image[0])
        source_color = image[sr][sc]

        while queue:
            size = len(queue)

            for i in range(size):
                x, y = queue.popleft()
                image[x][y] = color
                for r, c in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                    row = x + r
                    col = y + c

                    if row < 0 or row >= n or col < 0 or col >= m or image[row][col] != source_color or (row, col) in visited:
                        continue
                    visited.add((row, col))
                    queue.append((row, col))
        return image