昨天Roblox OA 最后一题 求解

项目描述：
https://docs.google.com/document ... -A/edit?usp=sharing
麻烦各位大佬帮我看一下这题怎么破。我只能想出一个暴力解法（时间复杂度为 （w*h)**n, 肯定不太好  )， 昨天在学院discord群里问，一位老哥建议用genetic algorithm :)
如果有想法的话，可以回复你的解法，任何语言，不过最好要过题目中的4个 test case。
谢谢

我觉得这个题，不需要BFS那么复杂？因为最后可行的office的位置，是近乎“均匀”分布在里面。所以，到office最远的停车场，一定是来自于四个角以及最中心的一个矩形（大小取决于w和h的奇偶）。之所以要考虑中心的矩形，是因为在遍历所有可能性的时候，如果office恰好落在四个角落，只算四个角的话，最远距离会是0。这样的话，复杂度就变成O(C(w *h, n) * n), where C() is combination. 示例代码如下，有问题欢迎继续讨论。

1. import itertools
   
2. 
   
3. def build_offices(w, h, n):
   
4.     points = [(0, 0), (0, w - 1), (h - 1, 0), (h - 1, w - 1)]
   
5.     for row in range((h - 1) // 2, h // 2 + 1):
   
6.         for col in range((w - 1) // 2, w // 2 + 1):
   
7.             points.append((row, col))
   
8. 
   
9.     all_pos = []
   
10.     for row in range(h):
    
11.         for col in range(w):
    
12.             all_pos.append((row, col))
    
13. 
    
14.     def get_farest(offices, points):
    
15.         res = 0
    
16.         for x, y in points:
    
17.             cur_nearest = float('inf')
    
18.             for row, col in offices:
    
19.                 cur_nearest = min(cur_nearest, abs(row - x) + abs(col - y))
    
20.             res = max(res, cur_nearest)
    
21.         return res
    
22. 
    
23.     res = float('inf')
    
24.     for comb in itertools.combinations(all_pos, n):
    
25.         cur = get_farest(comb, points)
    
26.         res = min(cur, res)
    
27. 
    
28.     return res
    
29. 
    
30. print(build_offices(4, 4, 3))
    
31. print(build_offices(2, 3, 4))
    
32. print(build_offices(4, 5, 1))
    
33. print(build_offices(3, 5, 2))

复制代码

nice problem, thank you

老胡拉夫斯基 发表于 2021-07-02 16:02:04
nice problem, thank you

Thank you

老胡拉夫斯基 发表于 2021-07-02 16:02:04
nice problem, thank you

You're welcome

我感觉用BFS围绕着office的位置为中心展开，中间check下已有的step数是否比当前的step小，就不继续在当点pos展开了。 大概O(n*w*h)

补充内容 (2021-08-06 13:53 +08:00):
图片传不了，四个case都过了，不知道
time complexity 过的了吗