讨论/求职面试/字节笔试题,求自助餐最佳摆放位置/
字节笔试题,求自助餐最佳摆放位置

说是有一个矩阵,0代表餐桌,1代表障碍物,求自助餐放在何处,离大家最近?有哪位大神有思路吗

12
共 12 个回复

多源bfs求交集?我的第一感觉.....

3

如果求所有人到某个非障碍物的距离总和,然后找到总和最小的那个位置,是否就是距离大家最近的点

是不是多源BFS啊

第一反应就是贪心去做。有没有demo案例看看

一维可以用贪心去考虑吧,简单推理一下就可以得到

好的,感谢。

大佬求解释

从每个人开始遍历,每遍历到一个地方(非障碍物),就给这个地方的数字加1,最后找到数字最小的地方(非零,不可以是障碍物)就是离大家最近的。
假设矩阵长宽分别为:m、n,共a个人
复杂度为:O(mna)

最短路径问题

这个是凸函数,x,y可以分离,你先在x轴
画两个点或者三个点理解下为什么要在中间,还不理解的话,采用凸优化的三分查找,爬山算法等,也能算出最优解。