LC1030 距离顺序排列矩阵单元格题解（生长方块）

昨天刷到一道题，做完后发现自己的解法和官方题解有一些差别，故分享一下

题目要求：

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

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

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

示例 1：

输入：rows = 1, cols = 2, rCenter = 0, cCenter = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]

示例 2：

输入：rows = 2, cols = 2, rCenter = 0, cCenter = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

示例 3：

输入：rows = 2, cols = 3, rCenter = 1, cCenter = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

提示：

1 <= rows, cols <= 100
0 <= rCenter < rows
0 <= cCenter < cols

官方题解：

基础的是二维矩阵存储曼哈顿距离，排序后输出
进阶一点，进行分桶排序，降低时间复杂度
几何法，从中心向外枚举曼哈顿距离，用广度优先搜索

我的思路图如下（生长方块）：

首先手动放置中心位置的上下左右四个方块（可能不足四个，根据输入情况）到队列中，它们有各自的方向，可以根据方向进行生长

每一轮生长的方块都放置到队列中，这样取出的方块与中心的曼哈顿距离正是从小到大

步骤是先从队列中取出方块，让方块生长，新方块放置到队尾，然后将此取出方块的坐标填入数组中

switch 处利用了穿透

我的代码如下：

class Solution {
    public static int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        GrowthBlock.rows = rows;
        GrowthBlock.cols = cols;
        int[][] answer = new int[rows * cols][2];
        answer[0][0] = rCenter;
        answer[0][1] = cCenter;
        int i = 1;
        Queue<GrowthBlock> blocks = new LinkedList<>();
        if (rCenter - 1 >= 0) {
            blocks.offer(new GrowthBlock(rCenter - 1, cCenter, 6));
        }
        if (rCenter + 1 < rows) {
            blocks.offer(new GrowthBlock(rCenter + 1, cCenter, 2));
        }
        if (cCenter - 1 >= 0) {
            blocks.offer(new GrowthBlock(rCenter, cCenter - 1, 0));
        }
        if (cCenter + 1 < cols) {
            blocks.offer(new GrowthBlock(rCenter, cCenter + 1, 4));
        }
        while (!blocks.isEmpty()) {
            GrowthBlock block = blocks.poll();//取出一个block
            answer[i++] = block.getInts();//输出到答案
            for (GrowthBlock b : block.growth()) {//生长并填入新的block
                blocks.offer(b);
            }
        }
        return answer;
    }
}

class GrowthBlock {//生长块
    public static int rows;
    public static int cols;
    byte x;
    byte y;
    byte growthDir;//生长方向

    //0右上 1右 2右下 3下 4左下 5左 6左上 7上
    public GrowthBlock(int x, int y, int growthDir) {
        this.x = (byte) x;
        this.y = (byte) y;
        this.growthDir = (byte) growthDir;
    }

    public int[] getInts() {//返回坐标
        return new int[]{x, y};
    }

    public List<GrowthBlock> growth() {//生长并返回
        List<GrowthBlock> bs=new ArrayList<>();
        switch (growthDir) {
            case 0:
                if (y - 1 >= 0) {
                    bs.add(new GrowthBlock(x, y - 1, 0));
                }
            case 1:
                if (x + 1 < rows) {
                    bs.add(new GrowthBlock(x + 1, y, 1));
                }
                break;
            case 2:
                if (x + 1 < rows) {
                    bs.add(new GrowthBlock(x + 1, y, 2));
                }
            case 3:
                if (y + 1 < cols) {
                    bs.add(new GrowthBlock(x, y + 1, 3));
                }
                break;
            case 4:
                if (y + 1 < cols) {
                    bs.add(new GrowthBlock(x, y + 1, 4));
                }
            case 5:
                if (x - 1 >= 0) {
                    bs.add(new GrowthBlock(x - 1, y, 5));
                }
                break;
            case 6:
                if (x - 1 >= 0) {
                    bs.add(new GrowthBlock(x - 1, y, 6));
                }
            case 7:
                if (y - 1 >= 0) {
                    bs.add(new GrowthBlock(x, y - 1, 7));
                }
                break;
        }
        return bs;
    }
}