# Build Post Office II

{% tabs %}
{% tab title="Java" %}

```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;
		}
}

```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Java" %}

```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;
		}	
}

```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://shangan.gitbook.io/algorithm/he-xin-suan-fa-200-ti/bfs/matrix/build-post-office-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.