1524. Reflect Across the Anti-Diagonal
An R by C grid is given. Reflect it in the ANTI-DIAGONAL, the line running
from the top-right corner to the bottom-left one, and print the result.
The answer has `C` rows and `R` columns, the same shape change a transpose produces.
1 2 3 -> 6 3
4 5 6 5 2
4 1
The top-right value 3 stays on the reflecting line and moves to the top-right of the answer; the bottom-left value 4 likewise stays at the bottom-left.
1 2 -> 4 2
3 4 3 1
1 2 3 4 -> 4 a single row becomes a single column, reversed
3
2
1
On a single row this agrees with the anticlockwise turn of problem 1516 and
disagrees with the clockwise turn of problem 1515, which gives 1 2 3 4 read
downwards. The three moves coincide in pairs on degenerate shapes and on
nothing else.
## What most people try first
Writing out[i][j] = g[C-1-j][R-1-i], which reads plausible and is out of
bounds: the first index of g must be a ROW index, bounded by R, and
C-1-j is bounded by C. On a 2 by 3 grid it reads row 2, which does not
exist. The two dimensions have to be kept straight in every index, and that is
where a square grid stops helping.
The second reflex is to reuse the main-diagonal reflection, the ordinary
transpose out[i][j] = g[j][i]. That is a DIFFERENT move: on the 2 by 3
example the transpose gives 1 4 / 2 5 / 3 6 and this problem wants
6 3 / 5 2 / 4 1.
## The index
Allocate C rows of R columns and fill by reading:
out[i][j] = g[R - 1 - j][C - 1 - i] for i in 0..C-1 and j in 0..R-1
Both source indices are counted from the far end, and the ROW index is the one
built from j.
## Why it is correct, and the identity behind it
Reflecting in the anti-diagonal is always the transpose followed by a half turn,
in either order, because composing the two maps gives exactly this one. The transpose sends (a, b) to (b, a) into a C by R grid;
a half turn of that grid sends (b, a) to (C-1-b, R-1-a). So the composite
sends (a, b) to (C-1-b, R-1-a), and inverting it gives the formula above.
Two checks that hold on every shape: applying this move twice returns the original grid, and applying it after the transpose gives the half turn of problem 1517.
## The cells that do not move
A cell is on the reflecting line when (i, j) maps to itself, which needs
i = C-1-j and j = R-1-i; both reduce to i + j = C - 1 together with
R = C. So on a non-square grid NO cell is fixed, even though the picture
suggests a line of them. That is a useful sanity check: if a supposedly
anti-diagonal reflection leaves cells where they were on a 2 by 3 grid, the
formula is wrong.
## Overflow
Nothing is combined and values fit in a signed 32 bit integer, whose limit is
2147483647.
## Cost
O(R C) time and O(R C) for the answer.
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 reflected grid as C lines of R integers each, separated by single spaces. Note the shape: the answer has C rows and R columns.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.