Travelling worm P46641


Statement
 

pdf   zip

thehtml

A worm moves on an n × m board, keeping the direction of its movement while possible. The worm cannot go out of the board, nor cross any obstacle, nor cross any square visited before. In these cases, the worm turns the direction of its movement 90 degrees to the right. If, even after turning 90 degrees, the worm cannot continue, it stops.

Implement a program that prints the squares visited by the worm. The worm starts in the central position of the board, moving upwards.

Input

Input consists of the description of the board. The first line contains the number of rows n and the number of columns m, both odd numbers greater than 2. Follow n lines, each with m characteres. A ‘.’ indicates a free position. An ‘*’ indicates an obstacle. The central position is always free.

Output

Print the board with a ’G’ on each position visited by the worm.

Public test cases
  • Input

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

    Output

    GGGGGGGGGGGGGGGGGGG
    G.............GG*.G
    G........*....GG..G
    G........GGGG*GG.*G
    G........G..G.GG..G
    G...........G.GG..G
    G...*.......G*GGGGG
    G...........G.....*
    GGGGGGGGGGGGG......
    
  • Input

    3 3
    .*.
    ...
    ...
    

    Output

    G*.
    GGG
    GGG
    
  • Input

    3 3
    .*.
    ..*
    ...
    

    Output

    .*.
    .G*
    ...
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++