BiruLyu
8/15/2017 - 5:10 PM

## 317. Shortest Distance from All Buildings(#TLE).java

``````public class Solution {
public int shortestDistance(int[][] grid) {
if (grid == null || grid[0].length == 0) return 0;
final int[] shift = new int[] {0, 1, 0, -1, 0};

int row  = grid.length, col = grid[0].length;
int[][] distance = new int[row][col];
int[][] reach = new int[row][col];
int buildingNum = 0;

for (int i = 0; i < row; i++) {
for (int j =0; j < col; j++) {
if (grid[i][j] == 1) {
buildingNum++;
Queue<int[]> myQueue = new LinkedList<int[]>();
myQueue.offer(new int[] {i,j});

boolean[][] isVisited = new boolean[row][col];
int level = 1;

while (!myQueue.isEmpty()) {
int qSize = myQueue.size();
for (int q = 0; q < qSize; q++) {
int[] curr = myQueue.poll();

for (int k = 0; k < 4; k++) {
int nextRow = curr[0] + shift[k];
int nextCol = curr[1] + shift[k + 1];

if (nextRow >= 0 && nextRow < row && nextCol >= 0 && nextCol < col
&& grid[nextRow][nextCol] == 0 && !isVisited[nextRow][nextCol]) {
//The shortest distance from [nextRow][nextCol] to thic building
// is 'level'.
distance[nextRow][nextCol] += level;
reach[nextRow][nextCol]++;

isVisited[nextRow][nextCol] = true;
myQueue.offer(new int[] {nextRow, nextCol});
}
}
}
level++;
}
}
}
}

int shortest = Integer.MAX_VALUE;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 0 && reach[i][j] == buildingNum) {
shortest = Math.min(shortest, distance[i][j]);
}
}
}

return shortest == Integer.MAX_VALUE ? -1 : shortest;

}
}``````
``````public class Solution {
public int shortestDistance(int[][] grid) {
if(grid==null||grid.length==0||grid[0].length==0){
return 0;
}
int m=grid.length;
int n=grid[0].length;
int[][] reach=new int[m][n];
int[][] distance=new int[m][n];
int housecount=0;

for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1){
housecount++;
}
}
}

for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1){
if(!helper(grid, reach, distance, housecount, m, n, i, j)){
return -1;
}
}
}
}

int min=Integer.MAX_VALUE;

for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==0&&reach[i][j]==housecount){
min=Math.min(min, distance[i][j]);
}
}
}
return min==Integer.MAX_VALUE?-1:min;
}

public boolean helper(int[][] grid, int[][] reach, int[][] distance, int housecount, int m, int n, int i, int j){
boolean[][] visit=new boolean[m][n];
Queue<int[]> queue=new LinkedList<int[]>();
queue.offer(new int[]{i,j});
int[] dx={1,-1,0,0};
int[] dy={0,0, 1, -1};
int count=1;
int level=0;
visit[i][j]=true;
while(!queue.isEmpty()){
int size=queue.size();
level++;
for(int k=0;k<size;k++){
int[] num=queue.poll();
int x=num[0];
int y=num[1];
for(int t=0;t<4;t++){
int nx=x+dx[t];
int ny=y+dy[t];
if(nx>=0&&ny>=0&&nx<m&&ny<n&&!(visit[nx][ny])){
if(grid[nx][ny]==0){
reach[nx][ny]++;
distance[nx][ny]+=level;
visit[nx][ny]=true;
queue.offer(new int[]{nx, ny});
}else if(grid[nx][ny]==1){
visit[nx][ny]=true;
count++;
}
}
}
}
}
return count==housecount;
}
}``````
``````public class Solution {
public int shortestDistance(int[][] grid) {
int minDistance = Integer.MAX_VALUE;
int m = grid.length;
int n = grid[0].length;
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
cnt++;
}
}
}
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
if (grid[row][col] == 0) {
int distance = search(grid, row, col, cnt);
if (distance != 0) {
minDistance = Math.min(distance, minDistance);
}
}
}
}
return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
}

private int search(int[][] grid, int row, int col, int cnt) {
Queue<Point> q = new LinkedList<>();
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
q.add(new Point(row, col, 0));
int totalDistance = 0;
while (!q.isEmpty()) {
Point point = q.poll();
int r = point.row;
int c = point.col;
int d = point.distance;
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == 2 || visited[r][c]) {
continue;
}
visited[r][c] = true;
if (grid[r][c] == 1) {
totalDistance += d;
cnt--;
continue;
}
q.add(new Point(r + 1, c, d + 1));
q.add(new Point(r - 1, c, d + 1));
q.add(new Point(r, c + 1, d + 1));
q.add(new Point(r, c - 1, d + 1));
}
return cnt == 0 ? totalDistance : Integer.MAX_VALUE;
}

public class Point {
int row;
int col;
int distance;
public Point(int row, int col, int distance) {
this.row = row;
this.col = col;
this.distance = distance;
}
}
}

/*
[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
[[1,2,0]]
[[0,2,1],[1,0,2],[0,1,0]]
[[1,1],[0,1]]
*/``````