Pulibot Maze Challenge

Seged University’s AI research team is hosting a robotics programming contest. Your friend Hanga is participating with her famous Hungarian Puli, Pulibot, in an arena represented by a maze. The maze is an (H+2)×(W+2) grid with outside cells acting as boundaries. Cells inside the maze (with row indices 0 to H-1 and column indices 0 to W-1) are either empty or obstacles. Every empty cell has a color represented by a nonnegative integer between 0 and Z_MAX (initially 0).

Pulibot is programmed to repeatedly sense its local surroundings and then execute a command. At each step when Pulibot is at an empty cell (r, c), it senses the state array S = [S[0], S[1], S[2], S[3], S[4]] where:

• S[0] is the state (color) of cell (r, c).
• S[1] is the state of the western neighbor (r, c-1).
• S[2] is the state of the southern neighbor (r+1, c).
• S[3] is the state of the eastern neighbor (r, c+1).
• S[4] is the state of the northern neighbor (r-1, c).

Based on the sensed states, Pulibot executes an instruction (Z, A): it sets the color of its current cell to Z and then performs the action A, which can either be staying in place, moving to one of the 4 neighbors, or terminating the program. In the contest, the rules enforce that after at most 500,000 steps, when Pulibot terminates, the coloring of empty cells must satisfy:

• There is a shortest path from (0,0) to (H-1,W-1) such that every empty cell on that path is colored 1.
• Every other empty cell remains colored 0.

Your task is to help Hanga program Pulibot. In our simulation, you are given the full maze layout (obstacles and free cells) and you need to compute the shortest path from (0,0) to (H-1,W-1). Then, output a grid in which for each empty cell on the shortest path, you print 1, for every other empty cell print 0, and for obstacle cells print an asterisk (*). If there are multiple shortest paths, output any one of them.

Note: The maze input does not include the outer boundary. It is guaranteed that (0,0) and (H-1,W-1) are empty and that at least one valid path exists.

inputFormat

The first line contains two integers H and W, representing the number of rows and columns of the maze.

Each of the next H lines contains a string of length W. In these strings, a . denotes an empty cell and a * denotes an obstacle. It is guaranteed that the top-left cell (0,0) and the bottom-right cell (H-1,W-1) are empty, and that there exists at least one path between them.

outputFormat

Output H lines, each containing W tokens separated by a space.

• If the cell is empty and is part of a shortest path from (0,0) to (H-1,W-1), output 1.
• If the cell is empty and not on the shortest path, output 0.
• If the cell is an obstacle, output an asterisk *.

If there are multiple shortest paths, any one of them is acceptable.

sample

3 3
...
.*.
...

1 1 1
0 * 1
0 0 1