Problem statement

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

Solution

Variation of Leetcode 0317. Shortest Distance from All Buildings, but be carefull with different notations.

Complexity

It is O(mnk) for time and O(mn) for space.

Code

class Solution:
    def solve(self, grid):
        m, n = len(grid), len(grid[0])
        
        def bfs(grd, x, y):
            queue = deque([(-1, x, y)])
            grd[x][y] = -1
            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] in [0, 2]:
                        grd[dr][dc] = dist - 1
                        queue.append((dist - 1, dr, dc))
            
            return grd
        
        total = [[0] * n for _ in range(m)]
        people = 0
        
        for x, y in product(range(m), range(n)):
            if grid[x][y] != 2: continue
            people += 1
            grd = [x[:] for x in grid]
            q = bfs(grd, x, y)
            
            for i,j in product(range(m), range(n)):
                if q[i][j] == 0: q[i][j] = -float("inf")
                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 -max(cands) - people