一道狗家面试题。infinite matrix search - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道狗家面试题。infinite matrix search

一道狗家面试题。infinite matrix search# JobHunting - 待字闺中

s*m2017-03-31 07:03

1 楼

有一个起点，有一个终点，可以0表示可以通过, 1表示墙，问从起点能不能到达终点
，出发能走16个方向，分别是 :x +-1, x +- 2, y +-1, y +- 2，
考虑到Matrix是infinite的，肯定不能无限DFS，
开始想的是算起点终点绝对距离，然后剪枝，想想也不对。大家有什么好的想法。

S*n2017-03-31 07:03

2 楼

bfs不行嘛？

l*z2017-03-31 07:03

3 楼

用一个min heap存任意点到终点的空间距离，从起点开始，加16个方向的点到heap。选
里面最短的出了继续搞，基本就是greedy加bfs吧

【在 s*******m 的大作中提到】

: 有一个起点，有一个终点，可以0表示可以通过, 1表示墙，问从起点能不能到达终点
: ，出发能走16个方向，分别是 :x +-1, x +- 2, y +-1, y +- 2，
: 考虑到Matrix是infinite的，肯定不能无限DFS，
: 开始想的是算起点终点绝对距离，然后剪枝，想想也不对。大家有什么好的想法。

W*o2017-03-31 07:03

4 楼

面经里见过这个题

g*d2017-03-31 07:03

5 楼

DJ stra 城市里面两个地点之间的路线就是用这个算的

z*n2017-03-31 07:03

6 楼

没明白，如果是无限大矩阵，那唯一的起点无法到达终点的情况就是墙把起点或者终点
彻底围起来了，是不是？如果是的话，遍历所有墙，检测是否包含终点起点就行了啊，
计算几何的简单问题。麻烦的地方就是你还能斜着走，算包含的时候得注意下。我这方
法没毛病吧？

p*g2017-03-31 07:03

7 楼

2点是否能通最好的算法就是dfs了, 用bfs怎么可能更快?

p*g2017-03-31 07:03

8 楼

你这个是找tsp, 对于2点是否能通, 毫无意义

【在 l*****z 的大作中提到】

: 用一个min heap存任意点到终点的空间距离，从起点开始，加16个方向的点到heap。选
: 里面最短的出了继续搞，基本就是greedy加bfs吧

l*z2017-03-31 07:03

9 楼

都说了不是简单的bfs,是吧BFS的queue换成min-heap.
其实应该两边同时走，这样如果一边及时发现被全环绕就直接退出为False就好了

【在 p*********g 的大作中提到】

: 2点是否能通最好的算法就是dfs了, 用bfs怎么可能更快?

i*92017-03-31 07:03

10 楼

这个是正解，画下搜索树的形状的话，双向搜索的搜索空间是单向搜索的一半。然后注
意设计hash函数就好了。

【在 l*****z 的大作中提到】

: 都说了不是简单的bfs,是吧BFS的queue换成min-heap.
: 其实应该两边同时走，这样如果一边及时发现被全环绕就直接退出为False就好了

p*g2017-03-31 07:03

11 楼

我也说了,minHeap的bfs是解决tsp的问题,对于2点直接是否可以走通, 意义不大

【在 l*****z 的大作中提到】

: 都说了不是简单的bfs,是吧BFS的queue换成min-heap.
: 其实应该两边同时走，这样如果一边及时发现被全环绕就直接退出为False就好了

a*62017-03-31 07:03

12 楼

Start from the start, try go to the end using shortest distance path
Return true if you hit the end
If you hit the wall, go around (dfs) and record the wall until you
eventually go back to where you hit the wall (which must happen)
There are 5 cases the wall you recorded will be like:
1) Encircles no points
2) Encricles points but not the start AND the end
3) Encricles the start AND the end
4) Encricles only the start
5) Encricles only the end
For the first 3 case, repeat step one, but instead of go from the start, go
form the point form the wall where it is the clostest to the end.
For the last 2 case, return false.