一道来源于GG一面的题目

cpcs 发表于 2014-12-5 14:25
这个题目比较有意思……
首先关于障碍的理解，其实原图就是一些点，障碍的点是孤立的，邻居关系就是边。 ...

曹神这题的方法能否写一个解题报告？ 给精。

我猜这题面试官想要的答案是二分答案 + bfs验证， max是不允许通过障碍的答案，min是起点和目标的x,y坐标绝对值差的和， 然后Binary Search答案用BFS验证是否存在小于等于3个障碍的路径存在。

北美农民 发表于 2015-1-11 03:54
曹神这题的方法能否写一个解题报告？ 给精。

我猜这题面试官想要的答案是二分答案 + bfs验证， max是 ...

bfs中记录经过几个障碍好像很麻烦诶，得重新建一个class？然后里面保存两个variable，一个是当前位置，另一个是从起点到当前位置经历了多少个障碍？有没有更好的方法？