Program to find number of minimum steps required to meet all person at any cell in Python

Suppose we have a 2D matrix where these values are present: 0 represents an empty cell. 1 represents a wall. 2 represents a person. Now a person can walk any of the four direction of up, down, left, right otherwise stay in one time unit. We have to find a walkable cell such that it minimizes the time it would take for everyone to meet and return the time. We have to keep in mind that two people can walk through the same empty cell and you can assume there is always some path between any two people.

So, if the input is like

then the output will be 2, as all can meet at position matrix[1, 1] with at most 2 steps.

To solve this, we will follow these steps −

• To solve this, we will follow these steps −

• Define a function bfs() . This will take r, c

• queue := define a queue and insert a pair (r, c) into it

• dist := a map with key value pair {(r, c) : 0}

• for each pair (r, c) in queue, do

  • if dist[r, c] > 15 is non−zero, then

    • come out from the loop

  • for each neighbor (nr, nc) of (r, c), do

    • if (nr, nc) is not in dist, then

      • dist[nr, nc] := dist[r, c] + 1

      • insert (nr, nc) at the end of queue

  • return dist

• From the main method do the following −

• dist := null

• for each row number r and corresponding row elements of A, do

  • for each column number c and value of row[c] val, do

    • if val is same as 2, then

      • ndist := bfs(r, c)

      • if dist is null, then

        • dist := ndist

      • otherwise,

        • for each key in keys of dist, do

          • if key is in ndist, then

            • dist[key] := maximum of dist[key], ndist[key]

          • otherwise,

            • remove dist[key]

• return minimum of all values of dist if dist is not empty, otherwise return 0

Example

 Live Demo

class Solution: def solve(self, A):    R, C = len(A), len(A[0])    def get_neighbor(r, c):       for nr, nc in ((r − 1, c), (r, c − 1), (r + 1, c), (r, c + 1)):          if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:             yield nr, nc       def bfs(r, c):          queue = [(r, c)]          dist = {(r, c): 0}          for r, c in queue:             if dist[r, c] > 15:                break             for nr, nc in get_neighbor(r, c):                if (nr, nc) not in dist:                   dist[nr, nc] = dist[r, c] + 1                   queue.append((nr, nc))          return dist       dist = None       for r, row in enumerate(A):          for c, val in enumerate(row):             if val == 2:                ndist = bfs(r, c)                if dist is None:                   dist = ndist                else:                   for key in list(dist.keys()):                      if key in ndist:                         dist[key] = max(dist[key],ndist[key])                      else:                         del dist[key]       return min(dist.values()) if dist else 0 ob = Solution() matrix = [    [2, 0, 1, 0],    [1, 0, 0, 2],    [2, 0, 2, 0] ] print(ob.solve(matrix))

Input

[    [2, 0, 1, 0],    [1, 0, 0, 2],    [2, 0, 2, 0] ]

Output

2