What is the approach to solve this question?

help
, ,
1

Could anyone suggest the approach to solve this question using BFS?

Question: https://leetcode.com/discuss/interview-question/221639/

Any other approaches are always welcome :slight_smile:

@everule1
@carre

2

“https://stackoverflow.com/questions/52562585/maximal-value-among-shortest-distances-in-a-matrix”

“ix1nh8 - Online C++0x Compiler & Debugging Tool - Ideone.com”

import itertools
from collections import deque
def buildOffice(height, width, n):
    arr = []
    for i in range(height):
        for j in range(width):
            arr.append((i,j,0))

    ans = float("inf")
    for points in itertools.combinations(arr,n):
        q = deque([]); visited = set()
        for m, n, dist in points:
            q.append((m,n,dist))
            visited.add((m,n))
        distAns = 0
        distArr = []
        while q:
            i, j, dist = q.popleft()
            distAns = max(dist, distAns)
            for x, y in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
                if 0<=x<height and 0<=y<width and (x,y) not in visited:
                    q.append((x,y,dist+1))
                    visited.add((x,y))
        ans = min(distAns, ans)

    return ans
3

Could you please explain your approach in brief.

4

what are the constraints or the expected complexity? I can’t found them. Another approach that may work (not sure without the constraints) is binary search the answer. Each step of the binary search you need to check if that answer is valid and to do that you just try to locate the points not further away than the current answer

5

Constraints are 1<=W<=H<=28 and 1<=n<=5. please explain your approach with code if possible.
Thank you :slight_smile:

6

It seems to me that you are looking for someone to solve the problem for you, am I wrong? A suggested approach is what I gave you, a code is a solution and I don’t think that I’m doing any good giving you the exact code :man_shrugging:t4:

7

Thank you! I have understood it now.

  1. We are placing our points at all possible positions.
  2. After all the points are placed in one configuration, we do BFS and find the maximum distance.
  3. Then we go with another configuration and repeat 2. Until we finish all configurations.
1 Like
8

Thank you! I have solved it now.