1512. Slide Every Diagonal Down
An R by C grid is given. Move every value one step down and to the right
along its own diagonal. The last value of each diagonal wraps round to become
the first. Print the resulting grid.
Cells are on the same diagonal when column - row is equal.
1 2 3 4 -> 11 12 8 4
5 6 7 8 10 1 2 3
9 10 11 12 9 5 6 7
The diagonal 1 6 11 becomes 11 1 6. The diagonal 4, which holds one
cell, is unchanged.
1 2 3 4 5 -> 1 2 3 4 5 every diagonal has one cell, so nothing moves
1 2 -> 4 2
3 4 3 1
## What most people try first
Writing g[i][j] = g[i-1][j-1] straight into the grid, top-left to
bottom-right. That destroys the diagonal: by the time row 2 is written, row 1
already holds row 0's values, so every value on the diagonal becomes the first
one. On the 3 by 4 example the diagonal 1 6 11 comes out as x 1 1.
Fixing it by walking bottom-right to top-left instead does work for the interior, and then the wrap is still missing: the cell at the START of each diagonal has no up-left neighbour and must receive the diagonal's LAST value.
## Write into a second grid and read only from the first
for each cell (i, j):
if i > 0 and j > 0:
out[i][j] = g[i-1][j-1]
else:
n = min(R - i, C - j) length of the diagonal starting here
out[i][j] = g[i + n - 1][j + n - 1]
## Why the second branch is exactly the wrap
A cell with i == 0 or j == 0 is always the topmost cell of its diagonal,
because stepping up and left from it leaves the grid and therefore cannot reach
an earlier cell. The diagonal starting at
(i, j) runs until one index hits an edge, so it holds min(R - i, C - j)
cells and its last one is at (i + n - 1, j + n - 1). Giving that value to the
start is the wrap, and the formula covers a diagonal of length one, where the
cell simply receives itself.
## Why the answer needs a second grid
Every cell both gives and takes a value, so any in-place order has a cell whose
old value is needed after it has been overwritten, unless the diagonal is
walked as a cycle carrying one value along. A second grid is O(R C) and the
cycle walk is O(1) extra; both are accepted here, and the cycle version is
the same trick problem 1505 uses on rings.
## Overflow
Nothing is combined, and values fit in a signed 32 bit integer, whose limit is
2147483647.
## Cost
O(R C) time, with one min on the cells that start a diagonal and a single
read elsewhere.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `-10^9 ≤ each value ≤ 10^9` - `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 grid after the slide: 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.