Problem statement

https://binarysearch.com/problems/The-Meeting-Place-Sequel/

Solution

Almost the same as Leetcode 0317. Shortest Distance from All Buildings.

Complexity

Time complexity is O(mnk), where k is number of person, space complexity is O(mn).

Code

class Solution:
    def solve(self, grid):
        m, n = len(grid), len(grid[0])
        
        def bfs(grd, x, y):
            queue = deque([(0, x, y)])
            while queue:
                dist, r, c = queue.popleft()
                for dr, dc in [(r, c+1), (r, c-1), (r-1, c), (r+1, c)]:
                    if 0 <= dr < m and 0 <= dc < n and grd[dr][dc] == 0 and (dr, dc) != (x, y):
                        grd[dr][dc] = dist + 1
                        queue.append((dist + 1, dr, dc))
            
            return grd
        
        total = [[0] * n for _ in range(m)]
        
        for x, y in product(range(m), range(n)):
            if grid[x][y] != 2: continue
                
            grd = [[int(x==1) for x in row] for row in grid]
            q = bfs(grd, x, y)
            for i, j in product(range(m), range(n)):
                if q[i][j] == 0 and (x, y) != (i, j): q[i][j] = float("inf")
                total[i][j] = max(total[i][j], q[i][j])

        cands = [total[x][y] for x, y in product(range(m), range(n)) if grid[x][y] != 1]
        return min(cands)