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

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

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

βhttps://ideone.com/ix1nh8β

```
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
```

Could you please explain your approach in brief.

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

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

Thank you

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

Thank you! I have understood it now.

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

1 Like

Thank you! I have solved it now.