1501. Ring by Ring, Outside In
An R by C grid is given. A RING is one boundary layer of it. Ring 0 is the
outer border. Ring 1 is the border of what is left once ring 0 is removed, and
so on inwards. There are (min(R, C) + 1) / 2 rings, rounded down.
Print each ring on its own line, CLOCKWISE, starting at that ring's own top-left cell. Every cell appears exactly once on exactly one line.
1 2 3 4 ring 0 -> 1 2 3 4 8 12 11 10 9 5
5 6 7 8 ring 1 -> 6 7
9 10 11 12
1 2 3 4 5 one ring only -> 1 2 3 4 5
1 2 ring 0 -> 1 2 4 3
3 4
## What most people try first
The four-boundary spiral loop from problem 64, with a line break inserted whenever the boundaries move. That is the right skeleton and it prints the wrong thing: in the 3 by 4 example above, the boundaries shrink four times per ring, so a break per boundary move gives four lines where there is one ring.
The other reflex is to compute a ring's cells as
top row + right column + bottom row + left column. On a ring that is a
single row, top and bottom are the SAME row and every value is printed twice.
The 1 by 5 example above is the smallest case that catches it, and a square
grid never produces one.
## Walk one ring at a time
Hold all four boundaries and move all four inward together, once per ring rather than once per side.
while top <= bot and left <= right:
emit g[top][left .. right] the top side
emit g[top+1 .. bot][right] the right side
if top < bot: emit g[bot][right-1 .. left]
if left < right: emit g[bot-1 .. top+1][left]
end the line
top++; bot--; left++; right--
## Why the two guards are exactly the right ones
The bottom side is a different row from the top side only when top < bot.
When they are equal the ring is one row tall and the top pass has already
emitted all of it. The same argument gives left < right for the left side.
Note the guards are STRICT: the usual spiral uses top <= bot, which is
correct there because the boundaries have already moved. Here they have not,
so <= would re-emit the row.
## The ring count
(min(R, C) + 1) / 2 rounded down, because each ring removes one row from
the top and one from the bottom, and the shorter side runs out first. A 3 by
4 grid has 2 rings; a 2 by 5 grid has 1.
## Overflow
Values reach 10^9 in magnitude, which fits in a signed 32 bit integer since
the limit is 2147483647. Nothing is added here, so nothing can overflow.
## Cost
O(R C) time, since every cell is emitted once, and O(R C) for the grid.
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 one line per ring, outermost ring first. Each line holds that ring's values in clockwise order starting at its top-left cell, separated by single spaces. There are (min(R, C) + 1) / 2 lines, rounded down.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.