// https://leetcode.com/problems/flood-fill/

import java.util.*;
import java.io.*;

class FloodFill {

    // helper structure
    public static class Node{
        int row;
        int col;

        Node(int row, int col){
            this.row = row;
            this.col = col;
        }
    }

    // DFS
    public static void dfs(int r, int c, boolean visited[][],
                           int image[][], int iniColor, int newColor){

        visited[r][c] = true;
        image[r][c] = newColor;

        int n = image.length;
        int m = image[0].length;

        int dr[] = {-1, 0, 1, 0};
        int dc[] = {0, 1, 0, -1};

        for(int k=0;k<4;k++){
            int nr = r + dr[k];
            int nc = c + dc[k];

            if(nr >= 0 && nr < n && nc >= 0 && nc < m &&
               !visited[nr][nc] && image[nr][nc] == iniColor){
                dfs(nr, nc, visited, image, iniColor, newColor);
            }
        }
    }


    // BFS
    public static void bfs(int r, int c, boolean visited[][],
                           int image[][], int iniColor, int newColor){

        visited[r][c] = true;
        image[r][c] = newColor;

        int n = image.length;
        int m = image[0].length;

        int dr[] = {-1, 0, 1, 0};
        int dc[] = {0, 1, 0, -1};

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(r, c));

        while(!q.isEmpty()){
            Node cur = q.poll();

            for(int k=0;k<4;k++){
                int nr = cur.row + dr[k];
                int nc = cur.col + dc[k];

                if(nr >= 0 && nr < n && nc >= 0 && nc < m &&
                   !visited[nr][nc] && image[nr][nc] == iniColor){

                    visited[nr][nc] = true;
                    image[nr][nc] = newColor;
                    q.add(new Node(nr, nc));
                }
            }
        }
    }


    // flood fill
    public static int[][] floodFill(int image[][], int sr, int sc, int newColor){

        int n = image.length;
        int m = image[0].length;

        boolean visited[][] = new boolean[n][m];
        int iniColor = image[sr][sc];

        if(iniColor == newColor) return image;

        // choose one
        bfs(sr, sc, visited, image, iniColor, newColor);
        // dfs(sr, sc, visited, image, iniColor, newColor);

        return image;
    }


    // driver
    public static void main(String args[]){

        int image[][] = {
            {1,1,1,0},
            {0,1,1,1},
            {1,0,1,1}
        };

        int sr = 1, sc = 2, newColor = 2;

        int ans[][] = floodFill(image, sr, sc, newColor);

        for(int i=0;i<ans.length;i++){
            for(int j=0;j<ans[0].length;j++){
                System.out.printf("%d ", ans[i][j]);
            }
            System.out.printf("\n");
        }
    }
}