A logistics warehouse uses an automated gravity sorter to route small packages toward one of several exit lanes at the bottom. The sorter is built from a rectangular grid of m rows and n columns of diagonal deflector panels, stacked directly on top of one another. Each panel is mounted in one of two orientations: a panel with value 1 is tilted so that any package sliding onto it is pushed one column to the right as it drops to the next row down; a panel with value -1 is tilted so that the package is pushed one column to the left.
A package gets physically wedged and never moves again if either of these happens as it tries to move: it would be pushed past the leftmost or rightmost column of the grid, or it lands in a pocket formed by two panels tilted toward each other — that is, a panel tilted 1 with a panel tilted -1 immediately to its right in the same row (or symmetrically, a panel tilted -1 with a panel tilted 1 immediately to its left).
For each of the n columns, a package is dropped from directly above that column at the top of the sorter and falls through row by row, redirected at each row by the panel it is currently above before advancing to the next row. Determine, for every starting column, either the column index at the bottom of the grid where the package exits, or -1 if the package gets wedged somewhere before reaching the bottom.
Line 1: two integers m and n — the number of rows and columns of the sorter. Next m lines: each contains n integers, each equal to 1 or -1, giving one row of the grid from top to bottom (values given left to right within the row).
Print n integers on one line, separated by single spaces: the exit column for a package dropped into starting column 0, 1, ..., n-1 respectively (0-indexed), or -1 for a starting column whose package gets wedged.
Example 1
Input
2 3 1 1 -1 -1 -1 -1
Expected
0 -1 -1
Explanation
Starting at column 0: at row 0 the panel is 1, pushing the package to column 1; the panel at row 0, column 1 is also 1 (not -1), so there is no pocket and the move succeeds. At row 1 the panel at column 1 is -1, pushing the package back to column 0; the panel at row 1, column 0 is -1 (not 1), so this move also succeeds. The package exits at column 0. Starting at column 1: at row 0 the panel is 1, which would push it to column 2, but the panel at row 0, column 2 is -1 — the two panels tilt toward each other, forming a pocket, so the package is wedged immediately (-1). Starting at column 2: at row 0 the panel is -1, which would push it to column 1, but the panel at row 0, column 1 is 1 — again a pocket, so the package is wedged immediately (-1). The output is 0 -1 -1.
Example 2
Input
2 5 1 1 1 1 1 1 1 1 1 1
Expected
2 3 4 -1 -1
Explanation
Every panel tilts 1 (push right), and no two adjacent panels here ever tilt toward each other, so a package only gets wedged by hitting the right wall. Starting at column c, row 0 pushes it to c+1 (valid as long as c+1 < 5) and row 1 pushes it to c+2 (valid as long as c+2 < 5). Columns 0, 1, 2 successfully reach columns 2, 3, 4. Column 3 reaches column 4 after row 0, but row 1 would push it to column 5, past the right wall, so it is wedged (-1). Column 4 is already pushed to column 5 at row 0, past the right wall, so it is wedged (-1) immediately. The output is 2 3 4 -1 -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →