Velociraptor is fit P22437


Statement
 

pdf   zip

thehtml

When a velociraptor does not smell human blood, takes advantage to do some exercise and mark its territory. In a rectangular room n × m with obstacles, our friend starts running trying to keep the direction and the sense of its movement while it is possible, leaving a pheromone trace. Under any circumstances it will go out of the room, nor will cross an obstacle, nor will cross a square that was crossed previously. In these cases, velociraptor will turn 90 degrees to the right. If, even turning 90 degrees, the velociraptor could not continue, it would stop.

Implement a program that prints the squares where the velociraptor has been before stopping. The velociraptor always starts in the central position of the room, moving towards north.

Input

The input describes a room. The first line has the number of rows n and the number of columns m. It is fulfilled that 2 < n, m < 200. n as well as m are odd numbers. n lines follow, with m characters each one. An asterisk indicates an obstacle. The central position is always free.

Output

Your program must print the board with a ’V’ in each position where the velociraptor has been.

Public test cases
  • Input

    9 19
    ...................
    ................*..
    .........*.........
    .............*...*.
    ...................
    ...................
    ....*........*.....
    ..................*
    ...................
    

    Output

    VVVVVVVVVVVVVVVVVVV
    V.............VV*.V
    V........*....VV..V
    V........VVVV*VV.*V
    V........V..V.VV..V
    V...........V.VV..V
    V...*.......V*VVVVV
    V...........V.....*
    VVVVVVVVVVVVV......
    
  • Input

    3 3
    .*.
    ...
    ...
    

    Output

    V*.
    VVV
    VVV
    
  • Input

    3 3
    .*.
    ..*
    ...
    

    Output

    .*.
    .V*
    ...
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++