Given a neighborhood and an arrangement of house plots where some of the plots have stores, some empty plots and the rest inaccessible,
identify a plot to build on that is accessible from all the stores and is the shortest total distance away from all the stores.
Also identify the total distance of all the stores from it. (You can only pass through empty plots)
ip:
0 0 0 1 0 0 0
0 2 0 0 0 0 0
1 0 0 1 2 0 1
Op: 10
Explanation:
closest plot is(1,3) and shorted distance to all 4 store is 1 + 1 + 4 + 4 = 10
Leetcode: #317 https://leetcode.com/problems/shortest-distance-from-all-buildings/
BFS Solution:
public int shortestDistance(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
int[][] dist=new int[m][n];
int[][] stores_visites=new int[m][n];
int visited=3, distance, stores=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
distance=1;
if(grid[i][j]==1){
stores++;
Queue<int[]> q=new LinkedList<>();
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
q.add(new int[]{i,j});
while(!q.isEmpty()){
int k=q.size();
while(k>0){
k--;
int[] cords=q.poll();
for(int[] d:dirs){
int x=cords[0]+d[0];
int y=cords[1]+d[1];
if(x<0 || y<0 || x>=m || y>=n || grid[x][y]==2 || grid[x][y]==1 || grid[x][y]==visited) continue;
grid[x][y]=visited;
dist[x][y]=dist[x][y]+distance;
stores_visites[x][y]++;
q.add(new int[]{x,y});
}
} //k while
distance++;
} //while
} //if
visited++;
}
}
int ans=Integer.MAX_VALUE;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(ans>dist[i][j] && stores_visites[i][j]==stores )
ans=dist[i][j];
}
}
return ans==Integer.MAX_VALUE ? -1 : ans;
}Comments (1)