Description
This problem is revised from example 6.26 of the textbook.
We place a number of two-sided mirrors at a −45° angle ("\" orientation) inside a rectangular room of width W and depth D.
The room boundary contains 2 × (W + D) windows, numbered in counterclockwise order starting from 0 at the bottom edge.
When a light ray enters the room from one window, it travels straight through the grid.
-
If the ray passes through an empty cell (
0), it continues in the same direction. -
If the ray encounters a mirror (
1), it is reflected according to the −45° mirror rule:-
Down → Right
-
Right → Down
-
Up → Left
-
Left → Up
-
The ray will eventually leave the room through another boundary window.
Your task is to simulate the ray’s path and determine, for each entry window, the corresponding exit window.
Input
-
The first line contains two integers W and D — the width and depth of the room.
-
The next D lines each contain W integers (0 or 1).
-
1means the cell contains a −45° mirror ("\"). -
0means the cell is empty.
-
-
The arrangement of the room can be seen in the following figure of Sample Input 1.
Constraint
1 ≤ W, D ≤ 500
Output
-
Print 2 × (W + D) lines.
-
The i-th line contains the window number where a ray entering from window i will exit.