Velocirráptors 101 P72222


Statement
 

pdf   zip

html

Estás a punto de tocar suelo después de tu primer salto en paracaídas, cuando descubres que alguien ha soltado una manada de velocirráptors en la pista de aterrizaje. En fin, qué se le va a hacer, estas cosas pasan. Ahora están todos quietecitos, pero tan pronto toques el suelo, sabes que se avalanzarán sobre tí siguiendo el camino más corto posible (son listos, los condenados), y que tú permanecerás inmóvil, atenazado por el terror y por la tela del paracaídas.

La pista de aterrizaje es rectangular. Marcamos con un punto los espacios libres, con una ‘V’ los velocirráptors, y con una ‘#’ aquellas casillas con obstáculos (tú no puedes aterrizar en ellos, y los velocirráptors no pueden atravesarlos). (Observa los juegos de prueba para hacerte una idea). Los velocirráptors, que tardan un segundo en recorrer una casilla, pueden desplazarse horizontal y verticalmente, pero no en diagonal. Se te pide que marques con una ‘X’ aquellas casillas libres en las que, aterrizando en ellas, maximizarías tu (breve, pero intenso) tiempo de vida restante.

Entrada

Un juego de pruebas contiene varios casos. Cada caso empieza con una línea con dos números F y C (las dimensiones en filas y columnas del mapa de la pista de aterrizaje). A continuación hay F filas de C caracteres cada una, con la descripción del mapa según se ha explicado anteriormente.

Se te garantiza que siempre existirá alguna casilla vacía en la que aterrizar, por lo que tu tiempo de vida siempre será mayor que 0, y que no hay espacios cerrados sin velocirráptors, es decir, que para cualquier casilla libre siempre existe un velocirráptor que puede llegar a ella, por lo que tu tiempo de vida no será infinito.

Salida Para cada caso, escribe el mapa donde marcarás con una ‘X’ aquellas casillas que, cayendo en ellas, maximizarían tu tiempo de vida. Separa dos mapas por una línea con 3 guiones ‘---’, como en el ejemplo.

Puntuación

  • Test1:   100 casos donde 2≤ F, C≤ 10.  25 Puntos 
  • Test1:   50 casos donde 2≤ F, C≤ 100.  40 Puntos 
  • Test1:   10 casos donde 2≤ F, C≤ 500.  35 Puntos 
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
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++