Flood Fill

1package pkg5leetcode.interview150;2 3/*4 * Flood Fill | LC 7335 * APPROACH: DFS/BFS paint connected same-color cells.6 * COMPLEXITY: Time O(m*n), Space O(m*n)7 */8public class interview150_LC733FloodFill {9    static int[][] floodFill(int[][] image, int sr, int sc, int color) {10        int orig = image[sr][sc];11        if (orig == color) return image;12        dfs(image, sr, sc, orig, color);13        return image;14    }15 16    static void dfs(int[][] img, int r, int c, int orig, int color) {17        if (r < 0 || c < 0 || r >= img.length || c >= img[0].length || img[r][c] != orig) return;18        img[r][c] = color;19        dfs(img, r + 1, c, orig, color);20        dfs(img, r - 1, c, orig, color);21        dfs(img, r, c + 1, orig, color);22        dfs(img, r, c - 1, orig, color);23    }24 25    public static void main(String[] args) {26        int[][] img = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};27        int[][] res = floodFill(img, 1, 1, 2);28        check(res[1][1] == 2 && res[0][0] == 2, "case1");29        System.out.println("all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}