Velociraptors 101 P72222


Statement
 

pdf   zip

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++