Build Post Office II

Java

public class Solution {
    /**
     * @param grid: a 2D grid
     * @return: An integer
     */
		public int shortestDistance(int[][] grid) {
			if (grid == null || grid.length == 0 || grid[0].length ==0) return -1;
		
			int ans = Integer.MAX_VALUE;
			for (int i = 0; i < grid.length; i++) {
				for (int j = 0; j < grid[0].length; j++) {
					if (grid[i][j] == 0) {
						ans = Math.min(ans, bfs(grid, i, j)); //模拟邮局	
					}
				}
			}
			return ans == Integer.MAX_VALUE ? -1 : ans;
		}
		private int bfs(int[][] grid, int sx, int sy) {
			Queue<Integer> qx = new LinkedList<>();
			Queue<Integer> qy = new LinkedList<>();
			boolean[][] v = new boolean[grid.length][grid[0].length];
			
			int[] dx = {0, 0, 1, -1};
			int[] dy = {1, -1, 0, 0};
		
		qx.offer(sx);
			qy.offer(sy);
			v[sx][sy] = true;                                     //棋盘类BFS的套路 
		
			int dist = 0;
			int sum = 0;
			while (!qx.isEmpty()) {
				dist++;
				int size = qx.size();
				for (int i = 0; i < size; i++) {
					int cx = qx.poll();
					int cy = qy.poll();
					for (int k = 0; k < 4; k++) {
						int nx = cx + dx[k];
						int ny = cy + dy[k];           //棋盘上求距离的套路
		if (0 <= nx && nx < grid.length && 0 <= ny && ny < grid[0].length && !v[nx][ny]) {
							v[nx][ny] = true;
							
							if (grid[nx][ny] == 1) {
								sum += dist; //内部引用，不dist--（对比僵尸题
							}
							if (grid[nx][ny] == 0) {
								qx.offer(nx);
								qy.offer(ny); //不讨论墙，就把墙排除掉了
							}
						}
					}
				}
			}
			for (int i = 0; i < grid.length; i++) {
				for (int j = 0; j < grid[0].length; j++) {
			if (grid[i][j] == 1 && !v[i][j]) {
				return Integer.MAX_VALUE;
			}
		}		
			}
			return sum;
		}
}

Java

//双向BFS优化
public class Solution {
    /**
     * @param graph: a list of Undirected graph node
     * @param A: nodeA
     * @param B: nodeB
     * @return:  the length of the shortest path
     */
		public int shortestPath(List<UndirectedGraphNode> graph, UndirectedGraphNode A, UndirectedGraphNode B) {
			if (graph == null) return 0;
			if (A == B) return 0;
			
				Queue<UndirectedGraphNode> sQue = new LinkedList<>();
				Set<UndirectedGraphNode> sSet = new HashSet<>();
				sQue.add(A);
				sSet.add(A);
				
				Queue<UndirectedGraphNode> eQue = new LinkedList<>();
				Set<UndirectedGraphNode> eSet = new HashSet<>();
				eQue.add(B);
				eSet.add(B);
		
				int len = 0;
				
				while (!sQue.isEmpty() || !eQue.isEmpty()) {
					len++;
					int sizeS = sQue.size();
					for (int i = 0; i < sizeS; i++) {
						UndirectedGraphNode curS = sQue.poll();
						for (UndirectedGraphNode neighbor : curS.neighbors) {
							if (sSet.contains(neighbor)) continue;
							if (eSet.contains(neighbor)) return len;
							sQue.offer(neighbor);
							sSet.add(neighbor);
						}
					}
					
					len++;
					int sizeE = eQue.size();
					for (int i = 0; i < sizeE; i++) {
						UndirectedGraphNode curE = eQue.poll();
						for (UndirectedGraphNode neighbor : curE.neighbors) {
							if (eSet.contains(neighbor)) continue;
							if (sSet.contains(neighbor)) return len;
							eQue.offer(neighbor);
							eSet.add(neighbor);
						}
					}
				}
				return -1;
		}	
}