西雅图的FB 面筋

douch 发表于 2017-7-11 15:07
lz对的 我傻x了 双向不会有死循环

双向的话怎么判断循环停止的条件？

熟狗脸 发表于 2017-7-13 20:06
即便单向BFS也不会死循环吧？可以用 Visited 这个 hashset 来判断是否已经走过某点

如果destination被障碍物包围了就会

kqxqx 发表于 2017-8-6 00:03
如果destination被障碍物包围了就会

即使是双向BFS也会死循环的。关键在于“无限大的国际象棋棋盘”。

当起点无法到达终点的时候未必一定要某个被包围，例如他们之间有一个宽度为2的无限长鸿沟。

其实当题目中一旦有“无限”的条件的话就一下子从计算上升到数学需要考虑的范畴了。这时BFS必须有一个设定的Stop Condition (e.g., maximum visited number of cells).

更简单的可以这么想：当棋盘无限时，你根本不可能在有限时间内探明那些障碍的位置，而每个障碍的位置都可能影响最终“走通”或“不通”的结果。所以，对于无限棋盘在有限时间内是不能可能有定论的，最多只能是在e.g., MAX=10000步BFS内不能到达。

fliu249 发表于 2017-7-13 12:36
应该是的，后来没时间和面试官确认了，就讲了一下思路

Follow-up: 请问是不是要计算一个reduced problem: 在只用*或连成一个数的最大值？

然后就可以归纳成原来的问题了。原来的问题是+divide之后和炼乘比，但现在要和用*或连成比

Recruiter说Seattle现在没有e4的head count了