Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (the number zero, one, two), find a place to build a post office so that the sum of the distance from the post office to all the houses is smallest.
Return the smallest sum of distance. Return -1 if it is not possible.
class Coordinate { int x; int y; public Coordinate(int x, int y) { this.x = x; this.y = y; }}public class Solution { /** * @param grid a 2D grid * @return an integer */ public int EMPTY = 0; public int HOUSE = 1; public int WALL = 2; public int n; public int m; public int[][] grid; //四个方向 public int[] directionX = {0, 0, 1, -1}; public int[] directionY = {1, -1, 0, 0}; //初始化n, m, grid PRivate void setGrid(int[][] grid) { this.n = grid.length; this.m = grid[0].length; this.grid = grid; } //获取1，0的坐标序列 private ArrayList<Coordinate> getCoordinates(int type) { ArrayList<Coordinate> coordinates = new ArrayList<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == type) { coordinates.add(new Coordinate(i, j)); } } } return coordinates; } //判断坐标是否valid private boolean inBound(int x, int y, int[][] grid) { int n = grid.length; int m = grid[0].length; return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0; } //从房子出发，累加房子到每个空白的距离 public int shortestDistance(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return -1; } setGrid(grid); ArrayList<Coordinate> house = getCoordinates(HOUSE); //累加数组 int[][] distanceSum = new int[n][m]; //标记房子来过的记录，如果最后记录！=房子的数目，则说明有些空白不可达 int[][] visited = new int[n][m]; for (Coordinate h : house) { bfsHelper(h, distanceSum, visited); } int shortest = Integer.MAX_VALUE; ArrayList<Coordinate> empty = getCoordinates(EMPTY); for (Coordinate e : empty) { if (visited[e.x][e.y] != house.size()) { continue; } shortest = Math.min(shortest, distanceSum[e.x][e.y]); } if (shortest == Integer.MAX_VALUE) { return -1; } return shortest; } private void bfsHelper(Coordinate target, int[][] distanceSum, int[][] visited) { Queue<Coordinate> queue = new LinkedList<>(); queue.offer(new Coordinate(target.x, target.y)); boolean[][] hash = new boolean[n][m]; hash[target.x][target.y] = true; int step = 0; while (!queue.isEmpty()) { step++; int size = queue.size(); for (int i = 0; i < size; i++) { Coordinate coor = queue.poll(); for (int j = 0; j < 4; j++) { Coordinate adj = new Coordinate( coor.x + directionX[j], coor.y + directionY[j] ); if (!inBound(adj.x, adj.y, grid)) { continue; } if (hash[adj.x][adj.y]) { continue; } queue.offer(adj); distanceSum[adj.x][adj.y] += step; visited[adj.x][adj.y]++; hash[adj.x][adj.y] = true; } } } }}新闻热点
疑难解答
