Matrix Cells in Distance Order
给一个点,按照曼哈顿距离排序所有矩阵上的点。讨论中直接sort的都是耍流氓-_-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public int[][] allCellsDistOrder(int R, int C, int r0, int c0) { int[][] d = {{0, 1}, {1, 0},{0, -1}, {-1, 0}}; int[][] res = new int[R*C][2]; int count = 0; Queue<int[]> q = new LinkedList<int[]>(); Set<String> check = new HashSet<String>(); q.add(new int[]{r0, c0}); check.add(r0+"|"+c0); while(!q.isEmpty()) { int[] t = q.poll(); res[count++] = t; for(int i = 0 ; i < d.length; i++) { int newR = t[0]+d[i][0]; int newC = t[1]+d[i][1]; if(newR < R && newR>=0 && newC < C && newC>=0 && !check.contains(newR+"|"+newC)){ q.add(new int[]{newR, newC}); check.add(newR+"|"+newC); } } } return res; } } |