An orchard is laid out as a rectangular grid of plots with R rows and C columns, rows and columns numbered starting from 0. A drip-irrigation controller sits at plot (r0, c0). The controller must schedule every plot in the orchard for watering such that plots closer to it (measured by Manhattan distance, i.e. |row - r0| + |col - c0|) are scheduled no later than farther ones.
Produce the full schedule: list all R * C plots ordered primarily by nondecreasing Manhattan distance from (r0, c0). Whenever two or more plots tie on distance, break the tie by ascending row number, and if rows also tie, by ascending column number.
A single line containing four integers R, C, r0, c0.
Print R * C lines. Each line contains two integers row col (space-separated), the coordinates of one plot, in the required order described above. Every plot must appear exactly once.
Example 1
Input
2 2 0 1
Expected
0 1 0 0 1 1 1 0
Explanation
Plots and distances from (0,1): (0,1)->0, (0,0)->1, (1,1)->1, (1,0)->2. Sorted by distance then row then column: (0,1) first, then the distance-1 tie between (0,0) and (1,1) resolved by row (row 0 before row 1), then (1,0) last.
Example 2
Input
1 4 0 2
Expected
0 2 0 1 0 3 0 0
Explanation
Single row, columns 0..3, controller at column 2. Distances: col0->2, col1->1, col2->0, col3->1. Order by distance: col2 (0), then the distance-1 tie between col1 and col3 broken by ascending column (col1 before col3), then col0 (distance 2).
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 →