Challenge: Paint Bucket

Lab Java Intermediate 20 points

A picture is a grid of letters. Clicking the paint bucket on a cell repaints that cell and every cell connected to it (up, down, left, right) that has the same letter, with the new letter. Write it recursively and print the new picture.

Input

Line 1: rows cols. Then rows lines of letters. Last line: r c newLetter (the clicked cell, from 0).

Output

The repainted grid.

Example

Input

4 5
..##.
.#..#
##...
.....
0 0 o

Output

oo##.
o#..#
##...
.....

Sample input available Sample output available

Editor

Java

Hints

Base cases: stop if you're off the grid or the cell isn't the original letter.

Repaint the cell, then call paint on the 4 neighbours. If the new letter equals the old one, do nothing at all.

Solution explanation

Every cell is repainted at most once, so it's O(rows × cols). The from != to check stops an endless loop when the colour wouldn't change.

Show solution

import java.util.Scanner;

public class Main {
    static char[][] grid;

    static void paint(int r, int c, char from, char to) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return;  // off the picture
        if (grid[r][c] != from) return;                                         // different colour
        grid[r][c] = to;
        paint(r + 1, c, from, to);
        paint(r - 1, c, from, to);
        paint(r, c + 1, from, to);
        paint(r, c - 1, from, to);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int rows = sc.nextInt(), cols = sc.nextInt();
        grid = new char[rows][];
        for (int i = 0; i < rows; i++) grid[i] = sc.next().toCharArray();
        int r = sc.nextInt(), c = sc.nextInt();
        char to = sc.next().charAt(0);
        char from = grid[r][c];
        if (from != to) paint(r, c, from, to);
        StringBuilder sb = new StringBuilder();
        for (char[] row : grid) sb.append(new String(row)).append('\n');
        System.out.print(sb);
    }
}

Output

Answer