Solution Explanation:

This problem asks to find the shortest total travel distance from a house to all buildings in a grid, where 0 represents empty land, 1 represents a building, and 2 represents an obstacle. The solution employs Breadth-First Search (BFS) to calculate the distances efficiently.

Approach:

1. Initialization:

   • total: Counts the number of buildings.
   • cnt: A 2D array to store the number of buildings reachable from each empty land.
   • dist: A 2D array to store the sum of distances from each empty land to all reachable buildings.

2. BFS from Each Building:

   • Iterate through the grid, and for each building (grid[i][j] == 1):
     • Perform BFS starting from that building.
     • For each empty land (grid[x][y] == 0) visited during BFS:
       • Increment cnt[x][y] (number of buildings reachable).
       • Add the distance (d) from the current building to dist[x][y].

3. Find Minimum Distance:

   • Iterate through the grid again.
   • For each empty land (grid[i][j] == 0):
     • If cnt[i][j] equals total (meaning it's reachable from all buildings):
       • Update the minimum distance ans with dist[i][j].

4. Return Result:

   • If ans remains unchanged (no such empty land found), return -1; otherwise, return ans.

Time Complexity Analysis:

The dominant part of the algorithm is the nested BFS loops. In the worst case, each BFS might visit all cells in the grid (O(mn)). Since we perform BFS from each building, the overall time complexity is O(b * m * n), where 'b' is the number of buildings and 'm' and 'n' are grid dimensions. In the worst-case scenario, b can be approximately equal to mn. Therefore the overall time complexity becomes approximately O(m² * n²).

Space Complexity Analysis:

The space complexity is dominated by the cnt, dist, and the queue used in BFS. The size of cnt and dist is O(m * n). The queue size in BFS can also be at most O(m * n). Therefore, the overall space complexity is O(m * n).

Code Explanation (Python):

The Python code directly implements the approach described above. The deque from the collections module is used for efficient queue operations in BFS. The code iterates through the grid, performing BFS from each building. It then finds the minimum distance among all empty lands reachable from all buildings.

Code Explanation (Java, C++, Go):

The Java, C++, and Go codes follow the same logic as the Python code. They utilize LinkedList (Java), queue (C++), and slices (Go) for queue implementation. The core BFS logic and distance calculations remain the same across all languages. Note that the C++ code uses pair<int, int> to represent coordinates for better readability. The Go code uses a boolean slice vis to efficiently track visited cells.