# Velociraptors 101 P72222

Statement

thehtml

You are on the point of arriving to the ground after your first jump in parachute, when you discover that somebody has released a group of velociraptors in the runway. Oh, well! This kind of things happen sometimes. Now, all of them are quiet, but as soon as you arrive to the ground, you know they will attack you following the shortest way (they are smart), and you will remain immobile, gripped by fear and the material of the parachute.

The runway is rectangular. We mark with a dot the empty spaces, with a ‘V’ the velociraptors, and with a ‘#’ the squares with obstacles (you cannot land there, and velociraptors cannot cross them). Observe the test data to get an idea. Velociraptors, that take a second to cover a square, can move horizontal and vertically, but not in diagonal. You are asked to mark with a ‘X’ the free squares where, landing in them, you will maximize your (brief but intense) remaining time life.

Input

A test data contains various cases. Each case starts with a line with two numbers R and C (dimensions in rows and columns of the runway map). Then, there are R rows of C characteres each one, with the description of the map as it has been previously explained.

We assure you that an empty square to land will always exist, therefore, your life time will always be greater than 0, and there is not any closed space without velocitaptors, that is, that for any empty square always exists a velociraptor that can reach it, so your life time will not be infinite.

Output For each case, your program must print the map where you will mark with a ‘X’ the squares that, landing in them, you will maximize your time life. Separate two maps by a line with 3 dashes ‘---’, as in the instance.

Scoring

• Test1:  ‍ 100 cases where 2≤ F, C≤ 10.  ‍25 Points ‍
• Test1:  ‍ 50 cases where 2≤ F, C≤ 100.  ‍40 Points ‍
• Test1:  ‍ 10 cases where 2≤ F, C≤ 500.  ‍35 Points ‍
Public test cases
• Input

```6 6
......
......
.V....
......
......
.....V

3 10
...#......
...#..#.V.
.V....#...

3 10
V###...V..
...#V.#.V.
.V.V.V#...

3 10
V###.V.V.V
..##V.#.V.
.V.V.V##.V
```

Output

```....XX
......
.V....
......
......
.....V
---
...#X.....
...#.X#.V.
.V....#...
---
V###.X.V.X
..X#V.#.V.
.V.V.V#X.X
---
V###XVXVXV
XX##VX#XVX
XVXVXV##XV
```
• Input

```6 6
VVVVVV
V....V
V....V
V....V
V....V
VVVVVV

6 5
VVVVV
V...V
V...V
V...V
V...V
VVVVV

5 6
......
......
...V..
......
......

5 6
VVVVVV
VVVV.V
V.VV.V
V.##.V
VVVVVV

5 6
VVVVVV
VVV.VV
VV...V
VVV.VV
VVVVVV
```

Output

```VVVVVV
V....V
V.XX.V
V.XX.V
V....V
VVVVVV
---
VVVVV
V...V
V.X.V
V.X.V
V...V
VVVVV
---
X.....
......
...V..
......
X.....
---
VVVVVV
VVVVXV
VXVVXV
VX##XV
VVVVVV
---
VVVVVV
VVV.VV
VV.X.V
VVV.VV
VVVVVV
```
• Input

```4 6
..#...
#.#V..
.V####
V.V...

9 9
.........
.#######.
.#.....#.
.#.###.#.
V#.#V#.#.
.#.###.#V
.#V....#.
.#######.
....V....
```

Output

```X.#..X
#.#V..
.V####
V.V..X
---
....XX...
.#######.
.#....X#.
.#.###.#.
V#.#V#.#.
.#.###.#V
.#V....#.
.#######.
....V....
```
• Input

```9 23
..#..........#.V.V.....
....#.#........V...V##.
.#..V....##V.#.#V......
...V...#.#.V..#.....#..
....#V.V.#.............
..##.V.............#...
.....#.#...#.#.#.#.....
......V....#.........V#
....V...#.............#

8 35
..VV.....#.........VV#.......V..#..
....V.............V.....V......V.V.
.......V.............#........V...V
...#.....V..V........V.............
....#.#.....V#...............V....V
.#...V.........................V#..
..........#........................
#.......#...#V......#......#..V....
```

Output

```..#..........#.V.V.....
....#.#........V...V##.
.#..V....##V.#.#V......
...V...#.#.V..#.....#..
....#V.V.#.............
..##.V.............#...
.....#.#...#.#.#.#.....
......V....#.........V#
....V...#.....X.......#
---
..VV.....#.........VV#.......V..#..
....V.............V.....V......V.V.
.......V.............#........V...V
...#.....V..V........V.............
....#.#.....V#...............V....V
X#...V.........................V#..
..........#........................
#.......#...#V......#....X.#..V....
```
• Information
Author
Omer Giménez
Language
English
Translator
Carlos Molina
Original language
Spanish
Other languages
Spanish
Official solutions
C++
User solutions
C++