-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathMatrix Cells in Distance Order
52 lines (47 loc) · 2.16 KB
/
Matrix Cells in Distance Order
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
{5}Matrix Cells in Distance Order
You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).
Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the smallest distance to the largest distance. You may return the answer in any order that satisfies this condition.
The distance between two 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]].
class Solution {
public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
int a[][]=new int[rows*cols][2];//for storing coordinates
int k=0;
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
a[k][0]=i;
a[k][1]=j;
k+=1;
}
}
Arrays.sort(a,new Comparator<int[]>()
{
@Override
public int compare(int a[],int b[])
{
int d1=(int)Math.abs(a[0]-rCenter)+(int)Math.abs(a[1]-cCenter);//distance of first point
int d2=(int)Math.abs(b[0]-rCenter)+(int)Math.abs(b[1]-cCenter);//distance of second point
if(d1>d2)return 1;
else if(d1<d2)return -1;
else return 0;
}
}
);
return a;
}
}