Google 电面和 onsite

难道要对e个器材，每个做bfs，存下到空间每点的距离，就要有e个m*n的矩阵，然后所有矩阵对应位置加起来再算空间最小值的点？

求问，第四题我的解法时间复杂度算下来要O(n^4)， n 为矩阵的长边
大家有没有什么优化的方法
谢了！

最后一题是不是所有位置围成图形的中心呢？

allen6432 发表于 2015-9-11 14:17
最后一题是不是所有位置围成图形的中心呢？

主要是有墙 所以不是中心
我觉得应该是从器材出发做bfs，然后更新每个点的距离和，复杂度应该是e*m*n。

ManitobaFarmer 发表于 2015-5-2 00:25
有点相似，具体定义可以在 Wiki 上找到。

这道题只要能得到每个 intersection 有且仅有一个数这个结论 ...

请问intersection是什么意思？可以贴下简单版的code吗？

对呀，对每一个点做一次bfs求最短路径的话复杂度O(n^3)了啊

补充内容 (2015-9-16 01:15):
。。是O(n^4)

kelvinzhong 发表于 2015-9-16 01:15
对呀，对每一个点做一次bfs求最短路径的话复杂度O(n^3)了啊

补充内容 (2015-9-16 01:15):

只需要对器材做BFS即可

wenqiang88 发表于 2015-9-16 01:26
只需要对器材做BFS即可

你的意思是对每一个存在的器材做一次bfs？ 然后求每个点对这个点到器材的距离相加最短？

kelvinzhong 发表于 2015-9-16 01:27
你的意思是对每一个存在的器材做一次bfs？ 然后求每个点对这个点到器材的距离相加最短？

我是这么想的，想不到更好的方法

wenqiang88 发表于 2015-9-16 01:34
我是这么想的，想不到更好的方法

你这个解法也是O(n^4)的e.