Mirror Restoration
Time limit2sMemory limit128 MB
Reconstruct an N by M grid of empty cells and '/' mirrors so that shooting rays from all 2N+2M boundary holes matches a given exit-hole permutation.
- Level
Hard8 of 10
- Topics
- Simulation, Backtracking, Implementation
- Solved
- No attempts yet
Problem
There is an N by M box. Each cell is either empty or contains a / mirror. A ray passing through an empty cell keeps moving in the same direction. At a mirror, a ray moving right turns upward, a ray moving upward turns right, a ray moving left turns downward, and a ray moving downward turns left.
The boundary of the box has 2N+2M holes. The left side is numbered from top to bottom as 1 through N, the bottom side from left to right as N+1 through N+M, the right side from bottom to top as N+M+1 through 2N+M, and the top side from right to left as 2N+M+1 through 2N+2M.
For every hole, you are given the number of the hole where a ray shot from it exits. Construct any box shape that realizes this information. Every input is guaranteed to have at least one solution.
Input
The first line contains two integers N and M (1 ≤ N, M ≤ 100).
The next 2N+2M lines describe holes 1 through 2N+2M in order. Each line contains the number of the hole where the ray shot from that hole exits.
Output
Print N lines describing the box. Each line must contain M integers separated by spaces. Print 0 for an empty cell and 1 for a cell containing a / mirror.
If several box shapes are possible, you may print any one of them.