Java 36ms BFS from each building, cumulate cost for each empty space


  • 0
    Y

    See code with comments below. Two tips for the cost[][] matrix

    1. cost == -1 marks unreachable empty space from previous BFS, so that it can be skipped in the current BFS; 2. cost == 0 are nodes not yet visited in the current BFS. If it remains 0 after the BFS is finished, reassign it as cost = -1

      public class Solution {

      public int shortestDistance(int[][] grid) {
      	// assuming that empty lands far outnumber buildings, do BFS from each
      	// building and update a matrix which records total distance from each 
      	// empty land to all buildings, find the min
      	// complexity: O(B(V+E) + V) where B is the number of buildings
      	if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
      		return -1;
      	}
      	int m = grid.length;
      	int n = grid[0].length;
      	int[][] cost = new int[m][n]; // BFS cost starting from each building
      	int[][] totalCost = new int[m][n]; // cumulative cost
      	for (int i = 0; i < m; i++) {
      		for (int j = 0; j < n; j++) {
      			if (grid[i][j] == 1) {
      				// BFS from building to all empty spaces
      				BFS(grid, cost, i, j);
      				// reset state for visited empty spaces
      				// also mark the unreachable empty spaces
      				// s.t. they won't be further considered
      				for (int ii = 0; ii < m; ii++) {
      					for (int jj = 0; jj < n; jj++) {
      						if (grid[ii][jj] == 0) {
      							if (cost[ii][jj] > 0) {
      								totalCost[ii][jj] += cost[ii][jj];
      								cost[ii][jj] = 0;
      							} else {
      								cost[ii][jj] = -1;
      								totalCost[ii][jj] = Integer.MAX_VALUE;
      							}
      						}
      					}
      				}
      			}
      		}
      	}
      	int min = Integer.MAX_VALUE;
      	for (int i = 0; i < m; i++) {
      		for (int j = 0; j < n; j++) {
      			if (grid[i][j] == 0) {
      				min = Math.min(min, totalCost[i][j]);
      			}
      		}
      	}
      	return min == Integer.MAX_VALUE ? -1 : min;
      }
      
      private void BFS(int[][] grid, int[][] cost, int i, int j) {
      	LinkedList<int[]> queue = new LinkedList<int[]>();
      	queue.offerLast(new int[]{i, j});
      	cost[i][j] = 0;
      	while (!queue.isEmpty()) {
      		int[] curr = queue.pollFirst();
      		int[][] moves = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
      		for (int[] m : moves) {
      			int iprime = curr[0] + m[0];
      			int jprime = curr[1] + m[1];
      			if (iprime >= 0 && iprime < grid.length &&
      					jprime >= 0 && jprime < grid[0].length &&
      					grid[iprime][jprime] == 0 &&
      					cost[iprime][jprime] == 0) {
      				cost[iprime][jprime] = cost[curr[0]][curr[1]] + 1;
      				queue.offerLast(new int[]{iprime, jprime});	
      			} 
      		}
      	}
      }
      

      }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.