Pacman P30641


Statement
 

pdf   zip

html

A pacman is moving inside an n × m rectangular board, which consists of cells with a pill, empty cells and walls. When the pacman moves into a cell (either empty or with a pill), he keeps moving in the same direction. The pacman eats the pills of the cells that he visits, so those cells become empty. Moving into a wall is forbidden: the pacman rebounds against walls, choosing any random direction (north, east, south or west) different from the current one. The pacman does all this forever.

Given a board and the initial position and direction of the pacman, can you compute which pills the pacman could eventually eat?

Input

Input consists of several cases. Each case begins with n and m, followed by n lines, each with m characters: a ‘.’ for a pill, an ‘X’ for a wall. (Initially, there are no empty cells.) There is exactly one character chosen from ‘N’, ‘E’, ‘S’ or ‘W’, denoting the initial position and direction of the pacman. All the border characters are walls. You can assume 3 ≤ n, m ≤ 500.

Output

Print every board replacing by spaces the pills that could be eaten by the pacman. Print a blank line after every case.

Public test cases
  • Input

    7 8
    XXXXXXXX
    X......X
    X......X
    X..W...X
    X......X
    X......X
    XXXXXXXX
    3 3
    XXX
    XNX
    XXX
    5 7
    XXXXXXX
    XXX.XXX
    X..S..X
    XXX.XXX
    XXXXXXX
    6 10
    XXXXXXXXXX
    X.X.X....X
    X...X....X
    XE.......X
    X...X....X
    XXXXXXXXXX
    

    Output

    XXXXXXXX
    X      X
    X .... X
    X      X
    X .... X
    X      X
    XXXXXXXX
    
    XXX
    X X
    XXX
    
    XXXXXXX
    XXX XXX
    X.. ..X
    XXX XXX
    XXXXXXX
    
    XXXXXXXXXX
    X X X    X
    X . X .. X
    X        X
    X   X    X
    XXXXXXXXXX
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Semifinal
    Date
    2012-06-30