Practice Flood fill and BFS with the exercise "Flood fill Example"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

Goal

Story:

The Resistance have made a map of Alderaan, the planet they are currently settled in. They have put defence towers with heavy armaments on specific places in their base. Princess Leia has asked for a map showing which defence tower is to operate when an enemy lands.

This map works on the following principle: whichever defence tower is closest to the spot where the enemy have landed, will operate. C3PO and R2D2 have been assigned the job of drafting this map. You must help them...

Of course, to make your job simpler, the map provided has been highly simplified to spots where enemy can land, and those where they can't.

-------------------------------------------------- xxx --------------------------------------------------

The Problem:

Given a grid consisting of ‘.’ (visitable points) and ‘#’ (un-visitable points), and other entities for the defence towers, output a map showing the area coverage of each tower, based on distance.

-------------------------------------------------- xxx --------------------------------------------------

Rules:

1. Each tower has an I.D., which is not '#', '.' or '+'. Note that 2 towers may have the same I.D..

2. If 2 towers can reach a spot at the exact same time, mark that spot '+', even if both towers share the same I.D..

3. Towers can't send troops through un-visitable spots ('#').

4. If a tower can get to a spot first, mark the spot by its I.D..

5. This is the legend:
(i) '.' = reachable nodes
(ii) '#' = unreachable nodes
(iii) any other character = a tower's I.D.

6. Troops sent out by the towers at a particular spot can immediately move by distance 1 in the cardinal directions, i.e. UP, DOWN, LEFT, RIGHT (diagonals not possible).

7. If a spot on the map cannot be accessed (regardless of whether it is visitable or not) assign that spot with the character it had in the original map.

-------------------------------------------------- xxx --------------------------------------------------

Example:

Consider the following grid:

...#.
A#...
#..B.
.....

At time = 1, they will reach…

A..#.
A#.B.
#.BBB
...B.

At time = 2, they will reach…

AA.#.
A#BBB
#BBBB
..BBB

At time = 3, they will reach…

AA+#B
A#BBB
#BBBB
.BBBB

(Note that, both A and B can reach spot (2,0) at time = 3, so that spot is made into ‘+’)

At time = 4, they will reach…

AA+#B
A#BBB
#BBBB
BBBBB

This is what your program must output.

Input

Line 1: An integer W, the width of the map
Line 2: An integer H, the height of the map
Next H lines: W characters in each line, the map

Output

First H lines: W characters in each line, the resulting map

Constraints

1 ≤ W, H ≤ 30

Example

Input

10
10
..#.#...##
#..#.#....
.........#
..#..#..#.
.......#..
..#.JEDI.#
..#.....#.
.....#..#.
..........
..........

Output

JJ#.#DDD##
#JJ#J#DDDD
JJJJJ+DDD#
JJ#JJ#DD#I
JJJJJED#II
JJ#JJEDII#
JJ#JJEDI#I
JJJJJ#DI#I
JJJJJ+DIII
JJJJJ+DIII

Solve it

A higher resolution is required to access the IDE