s*******m
发帖数: 52 | 1 有一个起点， 有一个终点，可以0表示可以通过, 1表示墙，问从起点能不能到达终点
， 出发能走16个方向，分别是 :x +-1, x +- 2, y +-1, y +- 2，
考虑到Matrix是infinite的，肯定不能无限DFS，
开始想的是算起点终点绝对距离，然后剪枝，想想也不对。大家有什么好的想法。 |
S********n
发帖数: 21 | |
l*****z
发帖数: 3022 | 3 用一个min heap存任意点到终点的空间距离，从起点开始，加16个方向的点到heap。选
里面最短的出了继续搞，基本就是greedy加bfs吧
【在 s*******m 的大作中提到】
: 有一个起点， 有一个终点，可以0表示可以通过, 1表示墙，问从起点能不能到达终点
: ， 出发能走16个方向，分别是 :x +-1, x +- 2, y +-1, y +- 2，
: 考虑到Matrix是infinite的，肯定不能无限DFS，
: 开始想的是算起点终点绝对距离，然后剪枝，想想也不对。大家有什么好的想法。
|
W***o
发帖数: 6519 | |
g******d
发帖数: 152 | 5 DJ stra 城市里面两个地点之间的路线就是用这个算的 |
z*********n
发帖数: 1451 | 6 没明白，如果是无限大矩阵，那唯一的起点无法到达终点的情况就是墙把起点或者终点
彻底围起来了，是不是？如果是的话，遍历所有墙，检测是否包含终点起点就行了啊，
计算几何的简单问题。麻烦的地方就是你还能斜着走，算包含的时候得注意下。我这方
法没毛病吧？ |
p*********g
发帖数: 2998 | 7 2点是否能通最好的算法就是dfs了, 用bfs怎么可能更快? |
p*********g
发帖数: 2998 | 8 你这个是找tsp, 对于2点是否能通, 毫无意义
【在 l*****z 的大作中提到】
: 用一个min heap存任意点到终点的空间距离，从起点开始，加16个方向的点到heap。选
: 里面最短的出了继续搞，基本就是greedy加bfs吧
|
l*****z
发帖数: 3022 | 9 都说了不是简单的bfs,是吧BFS的queue换成min-heap.
其实应该两边同时走，这样如果一边及时发现被全环绕就直接退出为False就好了
【在 p*********g 的大作中提到】
: 2点是否能通最好的算法就是dfs了, 用bfs怎么可能更快?
|
i*****9
发帖数: 3157 | 10 这个是正解，画下搜索树的形状的话，双向搜索的搜索空间是单向搜索的一半。然后注
意设计hash函数就好了。
【在 l*****z 的大作中提到】
: 都说了不是简单的bfs,是吧BFS的queue换成min-heap.
: 其实应该两边同时走，这样如果一边及时发现被全环绕就直接退出为False就好了
|
|
|
p*********g
发帖数: 2998 | 11 我也说了,minHeap的bfs是解决tsp的问题,对于2点直接是否可以走通, 意义不大
【在 l*****z 的大作中提到】
: 都说了不是简单的bfs,是吧BFS的queue换成min-heap.
: 其实应该两边同时走，这样如果一边及时发现被全环绕就直接退出为False就好了
|
a**6
发帖数: 4 | 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. |
s**********g
发帖数: 14942 | 13 无限大矩阵也就会有无限多的墙
如何遍历所有的墙？
【在 z*********n 的大作中提到】
: 没明白，如果是无限大矩阵，那唯一的起点无法到达终点的情况就是墙把起点或者终点
: 彻底围起来了，是不是？如果是的话，遍历所有墙，检测是否包含终点起点就行了啊，
: 计算几何的简单问题。麻烦的地方就是你还能斜着走，算包含的时候得注意下。我这方
: 法没毛病吧？
|
r*******y
发帖数: 270 | |
k****r
发帖数: 807 | 15 这题难道不是bibfd吗？从两个点走，两个set存每个点的next points，哪个set小，下
次走哪个set里面的点。。。。直到走出另一个set存在的点，or，走到set是空，意味
着走不到。 |
c******3
发帖数: 6509 | 16 平面是无限大，很有可能两个sets无限增长
【在 k****r 的大作中提到】
: 这题难道不是bibfd吗？从两个点走，两个set存每个点的next points，哪个set小，下
: 次走哪个set里面的点。。。。直到走出另一个set存在的点，or，走到set是空，意味
: 着走不到。
|
k****r
发帖数: 807 | 17 无限大的话，也不会无限增长的，随便画画图就知道了，要不就是其中一个被围起来了
，这种情况最后其中一个set是empty的； 要不就是set有重叠，没有第三种情况，那种
情况下的两个点无限远。。。。。。不成立。
【在 c******3 的大作中提到】
: 平面是无限大，很有可能两个sets无限增长
|
