1525. Zero Out Every Cross
An R by C grid is given. Wherever the ORIGINAL grid holds a zero, that
cell's entire row and entire column become zero. Print the result.
The rewriting must happen inside the grid: apart from a constant number of scalar variables, no extra storage is allowed. In particular, no copy of the grid, no list of the zero positions, and no array of flags per row or per column.
1 2 3 4 -> 1 0 3 4
5 0 7 8 0 0 0 0
9 10 11 12 9 0 11 12
1 2 3 -> 1 2 3 no zero anywhere, so nothing changes
4 5 6 4 5 6
0 0 0 0 -> 0 0 0 0
1 2 3 4 0 0 0 0
## What most people try first
Scanning the grid and clearing a cross the moment a zero is found. That is the
one approach that is certainly wrong: the zeros it writes are indistinguishable
from the zeros that were there to begin with, so the next one triggers another
cross, and the grid collapses. On the first example, clearing the cross at
(1,1) puts a zero at (0,1), which then clears column 1 and row 0, and the
answer comes out almost entirely zero.
This is the SENTINEL COLLISION, and it is the whole difficulty: the marker and the data are drawn from the same alphabet.
The correct-but-expensive repairs are a full copy of the grid, O(R C) extra,
or two boolean arrays, O(R + C) extra. The second is the usual accepted
answer. This problem asks for O(1).
## Store the flags inside the grid
Row 0 and column 0 can serve as the two flag arrays, because a row that must be
cleared will end up with its first cell zero anyway, and likewise for a column.
The only cell they disagree about is (0, 0), which belongs to both, so its
two roles have to be separated by two scalars.
``` row0 = true if any of g[0][0..C-1] is zero col0 = true if any of g[0..R-1][0] is zero
for i in 1..R-1, j in 1..C-1: if g[i][j] == 0: g[i][0] = 0; g[0][j] = 0
for i in 1..R-1, j in 1..C-1: if g[i][0] == 0 or g[0][j] == 0: g[i][j] = 0
if row0: clear the whole of row 0 if col0: clear the whole of column 0 ```
## Why the two scalars are necessary
Suppose only g[0][3] is zero. Column 3 must clear and row 0 must clear. The
marker for "column 3 clears" is g[0][3], which is already zero, and the
marker for "row 0 clears" would be g[0][0], which is a different cell, so
this case works. Now suppose only g[0][0] is zero: it means both "row 0
clears" and "column 0 clears" and there is nowhere to write the second fact.
Hence row0 and col0 are read BEFORE any marking and applied LAST.
## Why the first pass must skip row 0 and column 0
They are the storage. A zero found in row 0 during the marking pass would be
read back as a flag for a column that may not need clearing. That is why the
marking loop starts at (1,1) and the two edges are handled by the scalars.
## Why the second pass must also run last on the edges
Clearing row 0 first would destroy the column flags before the interior has used them. The order marking, interior, then edges is forced, and swapping the last two steps is the most common way to get this wrong after the sentinel problem itself is understood.
## Overflow
Nothing is combined. Values fit in a signed 32 bit integer, whose limit is
2147483647, and negative values are allowed, which is exactly why marking
with a minus sign is not an option here.
## Cost
O(R C) time and O(1) extra memory.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `-10^9 ≤ each value ≤ 10^9` - a cell clears its cross when the ORIGINAL grid holds a zero there - no extra array of any size; `O(1)` extra memory beyond the input - `R` and `C` are independent; the grid need not be square
Input
The first line contains two integers R and C.
Each of the next R lines contains C integers.
Output
Print the rewritten grid as R lines of C integers each, separated by single spaces. The shape is unchanged.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.