1.题目基本信息

1.1.题目描述

给定四个整数 rows , cols , rCenter 和 cCenter 。有一个 rows x cols 的矩阵，你在单元格上的坐标是 (rCenter, cCenter) 。

返回矩阵中的所有单元格的坐标，并按与 (rCenter, cCenter) 的 距离 从最小到最大的顺序排。你可以按 任何 满足此条件的顺序返回答案。

单元格(r1, c1) 和 (r2, c2) 之间的距离为|r1 - r2| + |c1 - c2|。

1.2.题目地址

https://leetcode.cn/problems/matrix-cells-in-distance-order/description/

2.解题方法

2.1.解题思路

几何法。可以观察得到距离中心点曼哈顿距离相等的点都在同一个斜正方形上

2.2.解题步骤

第一步，求出最长曼哈顿距离

第二步，枚举各个距离的斜正方形；从上顶点进行逆时针遍历，将合法的点加到结果数组中

3.解题代码

python代码

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        # 思路：几何法。可以观察得到距离中心点曼哈顿距离相等的点都在同一个斜正方形上
        dirs = [(1, 1), (1, -1), (-1, -1), (-1, 1)] # 从上端点顺时针旋转
        # 第一步，求出最长曼哈顿距离
        maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter)
        row, col = rCenter, cCenter
        result = [[row, col]]
        # 第二步，枚举各个距离的斜正方形；从上顶点进行逆时针遍历，将合法的点加到结果数组中
        # print("maxDist", maxDist)
        for dist in range(1, maxDist + 1):
            row -= 1
            for i, (dr, dc) in enumerate(dirs):
                # 边界点走到顶点退出while循环
                while (i % 2 == 0 and row != rCenter) or (i % 2 == 1 and col != cCenter):
                    if 0 <= row < rows and 0 <= col < cols:
                        result.append([row, col])
                    row += dr
                    col += dc
                    # print((row, col))
        return result

4.执行结果