Velociraptors 101 P72222
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
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....
- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++