You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:
- Each 0 marks an empty land which you can pass by freely.
- Each 1 marks a building which you cannot pass through.
- Each 2 marks an obstacle which you cannot pass through.
Example:
Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]] 1 - 0 - 2 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0 Output: 7 Explanation: Given three buildings at(0,0)
,(0,4)
,(2,2)
, and an obstacle at(0,2), t
he point(1,2)
is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.
Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.
--------------------------------------There will be at least one building. If it is not possible to build such house according to the above rules, return -1.
难道在有障碍,所以最后选择了brute force, 从每一个building出发做bfs,把所有点的结果加起来找一个最小值。O(k * m * n),k为building的个数,m、n为长宽
隐藏的一个附加条件是,从最后的点必须能走到所有的building,所有额外用了一个参数来记录当前处理过的building的个数,每一次bfs都只尝试之前已经被走过的点。
class Solution { public int shortestDistance(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] rt = new int[m][n]; int building = 1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { building--; bfs(i, j, rt, grid, building); } } } return findTheShortest(rt, grid, building - 1); } private int findTheShortest(int[][] rt, int[][] grid, int building) { int shortest = Integer.MAX_VALUE; boolean found = false; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == building) { shortest = Math.min(rt[i][j], shortest); found = true; } } } return found ? shortest : -1; } private void bfs(int row, int col, int[][] rt, int[][] grid, int building) { int m = grid.length; int n = grid[0].length; boolean[][] visited = new boolean[m][n]; Queue<Tuple> que = new LinkedList<>(); que.add(new Tuple(row, col, 0)); grid[row][col] = building; while (!que.isEmpty()) { Tuple top = que.poll(); if (isNotValid(top, m, n, grid, visited, building)) { continue; } rt[top.row][top.col] += top.dis; visited[top.row][top.col] = true; grid[top.row][top.col] = building - 1; que.add(new Tuple(top.row + 1, top.col, top.dis + 1)); que.add(new Tuple(top.row, top.col + 1, top.dis + 1)); que.add(new Tuple(top.row - 1, top.col, top.dis + 1)); que.add(new Tuple(top.row, top.col - 1, top.dis + 1)); } grid[row][col] = 1; } private boolean isNotValid(Tuple t, int m, int n, int[][] grid, boolean[][] visited, int building) { int i = t.row, j = t.col; return i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j] != building; } } class Tuple{ public int row; public int col; public int dis; public Tuple(int row, int col, int dis) { this.row = row; this.col = col; this.dis = dis; } }
No comments:
Post a Comment