#1030

Matrix Cells in Distance Order

newbie · 280 · lc easy +20 · verified · 73.9% accepted · 815 likes · top 84%

Description

You are given integers rows, cols, rCenter, and cCenter. A rows x cols matrix exists, and you stand at cell (rCenter, cCenter).

Return all cell coordinates sorted by Manhattan distance from (rCenter, cCenter) in ascending order. Ties may be broken arbitrarily.

The Manhattan distance between cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

Example 1:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0

Output: [[0,0],[0,1]]

Explanation: The distances from (0, 0) to other cells are: [0,1]

Example 2:

Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1

Output: [[0,1],[0,0],[1,1],[1,0]]

Explanation: The distances from (0, 1) to other cells are: [0,1,1,2]

The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.

Example 3:

Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2

Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3]

There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].

Code

1

2

3

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]: