LeetCode(50) -- 1030,

P1030. Matrix Cells in Distance Order (Easy)

矩阵中给一个点，按曼哈顿距离从小到大的顺序排列所有的点的坐标。

我的思路

围着这个点转一圈，找出所有点的坐标，就是曼哈顿距离相同的所有点。然后曼哈顿距离加1，就找出外面一圈的所有点的坐标。这些点如果在矩阵的合法范围内，就排列进结果集合中。

我的代码

public class E_1030_MatrixCellsInDistanceOrder {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int n = R * C;
        int[][] ans = new int[n][2];
        int next = 0;

        int[] point = {r0, c0};
        ans[next] = point;
        next++;

        for (int manhattanDistance = 1; manhattanDistance < R + C; manhattanDistance++) {
            if (next < n) {
                next = fillOneCircle(ans, next, manhattanDistance, R, C, r0, c0 - manhattanDistance, 1, 1);
                next = fillOneCircle(ans, next, manhattanDistance, R, C, r0 + manhattanDistance, c0, -1, 1);
                next = fillOneCircle(ans, next, manhattanDistance, R, C, r0, c0 + manhattanDistance, -1, -1);
                next = fillOneCircle(ans, next, manhattanDistance, R, C, r0 - manhattanDistance, c0, 1, -1);
            }
        }
        return ans;
    }

    private boolean inMatrix(int R, int C, int r, int c) {
        return r >= 0 && r < R & c >= 0 && c < C;
    }

    private int fillOneCircle(int[][] ans, int next, int distance, int R, int C, int r0, int c0, int p1, int p2) {
        for (int i = 0; i < distance; i++) {
            int pointR = r0 + i * p1;
            int pointC = c0 + i * p2;
            if (inMatrix(R, C, pointR, pointC)) {
                int[] point = {pointR, pointC};
                ans[next] = point;
                next++;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        int[][] ints = new E_1030_MatrixCellsInDistanceOrder().allCellsDistOrder(2, 3, 1, 2);
        System.out.println("ints = " + Arrays.deepToString(ints));
    }
}

99%

最优解

class Solution {
    private void func(int x, int y, int R, int C, int offset, int index, int[][] arr) {
        if(index == R*C) return;
        int _x = x - offset, ly = y, ry = y, op = -1;
        if (_x >= 0 && _x < R) arr[index++] = new int[]{_x, y};

        do {
            _x++;
            ly += op;
            ry -= op;
            if (ly == ry) break;
            if (_x >= 0 && _x < R) {
                if (ly >= 0) arr[index++] = new int[]{_x, ly};
                if (ry < C) arr[index++] = new int[]{_x, ry};
            }
            if (x == _x) op = 1;
        } while (ly != ry);
        if (_x >= 0 && _x < R && ly >= 0 && ly < C) arr[index++] = new int[]{_x, ly};
        func(x, y, R, C, offset + 1, index, arr);

    }

    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int[][] res = new int[R * C][];
        res[0] = new int[]{r0, c0};
        func(r0, c0, R, C, 1, 1, res);
        return res;
    }
}

回来有时间再仔细看吧。。。