1162 compare to 317

Why LeetCode 317 Needs to Run BFS for Each House:

In LeetCode 317, the goal is to find a single piece of land that minimizes the total distance to all buildings. Since the distance has to be calculated from each building (house), you need to run BFS from every building to calculate the cumulative distance to every empty land.

Explanation:

1. Multi-source, all-destination problem: You need the distance from each building to all empty land (0). Each building is a separate source for BFS.

2. Separate BFS for each house: BFS is run from every building because each building is an independent source of distance. You need to know the distance from all buildings to every potential piece of land.

3. Summing distances: For every land (0), you sum the distances from all the buildings (1). This requires knowing the distance from each building separately.

4. Obstacle management: Some parts of the grid are blocked by obstacles (2), so BFS from each building needs to account for the layout of the grid independently.

Because of this, BFS has to be run from each building to accumulate the distance sums correctly.

Why LeetCode 1162 Does Not Need to Run BFS for Each Land Cell:

In LeetCode 1162, the goal is to find the water cell that is farthest from any land. This is conceptually different because you're looking for the farthest distance from the nearest land rather than the sum of distances from multiple lands.

Explanation:

1. Multi-source, single-destination problem: You want to find the water cell that is farthest from any land. The key here is that you're only concerned about the nearest land, not the combined distances from multiple land cells.

2. Single BFS with multiple sources: You can treat all land cells (1) as the sources and run a single BFS that starts from all land cells simultaneously. As BFS expands, it will propagate distance values outward from each land cell.

3. Water cells found first are closest to land: BFS guarantees that the first time you reach a water cell (0), it will be at the shortest distance from any land. By continuing the BFS, you progressively explore farther water cells.

4. Maximizing distance: You only need to keep track of the farthest water cell found during BFS, not the cumulative distance from multiple sources.