[force deduction] 1030. Arrange matrix cells in distance order

Given four integers row ,   cols ,  rCenter and cCenter . There is one  rows x cols  Matrix , Your coordinates on the cell are  (rCenter, cCenter) .

Returns the coordinates of all cells in the matrix , And press and  (rCenter, cCenter)  Of distance From the smallest to the largest . You can press whatever The answers are returned in the order that this condition is met .

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

Example 1：

Input ：rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output ：[[0,0],[0,1]]
explain ： from (r0, c0) The distance to other cells is ：[0,1]

Example 2：

Input ：rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output ：[[0,1],[0,0],[1,1],[1,0]]
explain ： from (r0, c0) The distance to other cells is ：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] It will also be seen as the right answer .

Example 3：

Input ：rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output ：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
explain ： from (r0, c0) The distance to other cells is ：[0,1,1,2,2,3]
Other answers that meet the requirements of the questions will also be considered correct , for example [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].

Tips ：

1 <= rows, cols <= 100
0 <= rCenter < rows
0 <= cCenter < cols （ This point must be within the range of matrix cells ）

class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int[][] arr=new int[rows*cols][2];// Define a two-dimensional array that stores the returned results 
        int index=0;// The subscript of a one-dimensional array in a two-dimensional array 
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                arr[index++]=new int[]{i,j};// Traverse to get all the coordinates 
            }
        }
        // Sort 
        Arrays.sort(arr,new Comparator<int[]>(){  // The comparator 
            @Override
            public int compare(int[] r0,int[] r1){ // One dimensional array 
                int l1=Math.abs(r0[0]-rCenter)+Math.abs(r0[1]-cCenter);
                int l2=Math.abs(r1[0]-rCenter)+Math.abs(r1[1]-cCenter);
                return l1-l2;
            }
        });
        return arr;
    }
}

 

Answer key ：

① Define a two-dimensional array arr: The number of one-dimensional arrays in a two-dimensional array is rows*cols, The length of one-dimensional array is 2;

② Through double for Cycle to save all coordinates to a two-dimensional array arr in ;

③ Sort ： Use Arrays.sort(T[ ] a, Comparator>? super T<> c) Sort

When calling this method to sort a custom array , We need to specify an external comparator . The second parameter is the custom comparator class , This class must inherit Comparator Interface and Implementation compare Method , So it's right T[] Sort according to the custom comparator rules .

This sort is guaranteed to be stable ： Equal elements will not be reordered by the sorting result .

To input ：rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output ：[[0,1],[0,0],[1,1],[1,0]] For example

Put all the coordinates , Compare the two , Each uses a distance formula |r1 - r2| + |c1 - c2| And target coordinates (rCenter, cCenter) Calculate , Finally, make a difference between the two groups , Return the comparator result , As arr Sort by .

namely ： All combinations

Comparing the two	[0,1],[0,0]	[1,0],[0,1]	[1,0],[0,0]	[1,1],[0,0]	[1,1],[1,0]
l1-l2( Distance difference )	-1	2	1	0	-1

Array.sort() Sort two-dimensional arrays
Each row of a two-dimensional array has two elements , How to use two-dimensional array i Arrange the elements of the column ？

for example , Right. 0 The elements of the column are arranged in ascending order ：

int[][] temp=new int[][]{ {3,6},{2,4},{1,5},{4,9}};
        Arrays.sort(temp, new Comparator<int[]>(){

            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }

        });
        for(int i=0;i<temp.length;i++){
            System.out.println(Arrays.toString(temp[i]));    
        }

Output ：
[1, 5]
[2, 4]
[3, 6]
[4, 9]
If to the second 1 The ascending arrangement of column elements only needs return o1[1]-o2[1];