203. Cells by Distance
A rows by cols floor is covered with square tiles. A speaker is mounted on the tile at row r0, column c0. The walking distance from the speaker to the tile at (r, c) is |r - r0| + |c - c0|.
List every tile as [r, c], ordered by walking distance from the speaker, nearest first. When several tiles are the same distance away, the one with the smaller row comes first, and if the rows are equal, the one with the smaller column comes first. Return the list of all rows * cols tiles in that order.
Example 1
- Input:
- rows = 2cols = 3r0 = 0c0 = 1
- Output:
- [[0,1],[0,0],[0,2],[1,1],[1,0],[1,2]]
- Explanation:
Distances from (0,1): (0,1)=0; (0,0),(0,2),(1,1)=1; (1,0),(1,2)=2. Ties are broken by row, then column.
Example 2
- Input:
- rows = 1cols = 1r0 = 0c0 = 0
- Output:
- [[0,0]]
- Explanation:
There is only one tile.
Example 3
- Input:
- rows = 3cols = 1r0 = 2c0 = 0
- Output:
- [[2,0],[1,0],[0,0]]
- Explanation:
The tiles in one column are ordered by how far they are from row 2: rows 2, 1, 0.
Constraints
1 ≤ rows, cols ≤ 100
0 ≤ r0 < rows
0 ≤ c0 < cols
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(R × C log(R × C))
- Space
- O(R × C)