1 public class Solution { 2 public int shortestDistance(int[][] grid) { 3 if (grid.length == 0 || grid[0].length == 0) { 4 return -1; 5 } 6 7 int[] shift = new int[]{0, 1, 0, -1, 0}; 8 int[][] distance = new int[grid.length][grid[0].length]; 9 int[][] reach = new int[grid.length][grid[0].length];10 int numBuildings = 0;11 for (int i = 0; i < grid.length; i++) {12 for (int j = 0; j < grid[0].length; j++) {13 if (grid[i][j] == 1) {14 int level = 1;15 numBuildings++;16 boolean[][] visited = new boolean[grid.length][grid[0].length];17 Queue queue = new LinkedList<>();18 queue.offer(new int[]{i, j});19 while (!queue.isEmpty()) {20 int size = queue.size();21 for (int k = 0; k < size; k++) {22 int[] current = queue.poll();23 for (int l = 0; l < 4; l++) {24 int x = current[0] + shift[l];25 int y = current[1] + shift[l + 1];26 if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && !visited[x][y] && grid[x][y] == 0) {27 visited[x][y] = true;28 distance[x][y] += level;29 reach[x][y]++;30 queue.offer(new int[]{x, y});31 }32 }33 }34 level++;35 }36 }37 }38 }39 40 int result = Integer.MAX_VALUE;41 for (int i = 0; i < grid.length; i++) {42 for (int j = 0; j < grid[0].length; j++) {43 if (grid[i][j] == 0 && reach[i][j] == numBuildings) {44 result = Math.min(result, distance[i][j]);45 }46 }47 }48 return result == Integer.MAX_VALUE ? -1 : result;49 }50 } Basic idea:
1. starting from each element expanding to all map. Find a 0, add one to reach, and level traversal to.
2. Go through each element again. Find the smallest distances.