l******t
发帖数: 37 | 1 原题如下：
Given a map which has some obstacles in it. Given a starting point S and
ending point E, find the shortest path from S to E. Note you can choose
any(4) direction from S, but during the process, you can only go straight
from the previous direction, unless you hit an obstacle.
看完题目能想到BFS，但是要完全按照题目要求实现有些困惑。求大牛指点啊
网上搜索类似问题，甚至涉及到一些算法，包括A*，是不是有点'过'了？ |
w********s
发帖数: 1570 | 2 如果没有obstacles，你应该知道怎么做吧，bfs
如果有obstacles，就相当于某些点到点的距离为INT_MAX，算法可以一样。
【在 l******t 的大作中提到】
: 原题如下：
: Given a map which has some obstacles in it. Given a starting point S and
: ending point E, find the shortest path from S to E. Note you can choose
: any(4) direction from S, but during the process, you can only go straight
: from the previous direction, unless you hit an obstacle.
: 看完题目能想到BFS，但是要完全按照题目要求实现有些困惑。求大牛指点啊
: 网上搜索类似问题，甚至涉及到一些算法，包括A*，是不是有点'过'了？
|
r****s
发帖数: 1025 | 3 recursioin/dp.
每个point有四个值，left, right, up, down,初始化，比如left=0可以左走，left=1
不可以向左走。
接下来的就简单了。 找最小的recursion。
stopping condition；
1. total step <= 长x宽
2. 找到e。
这是正确答案，或者之一。 |
c*****n
发帖数: 53 | 4 O(n^2)
sliding window to find up/down/left/right obstacle for each point
+
bfs |
l***i
发帖数: 1309 | |
l*********8
发帖数: 4642 | 6 re
【在 l***i 的大作中提到】
: dijkstra
|
p***e
发帖数: 111 | 7 dfs也可以解最短路径的问题，这个题的要求实际上是在提示用dfs。
【在 l******t 的大作中提到】
: 原题如下：
: Given a map which has some obstacles in it. Given a starting point S and
: ending point E, find the shortest path from S to E. Note you can choose
: any(4) direction from S, but during the process, you can only go straight
: from the previous direction, unless you hit an obstacle.
: 看完题目能想到BFS，但是要完全按照题目要求实现有些困惑。求大牛指点啊
: 网上搜索类似问题，甚至涉及到一些算法，包括A*，是不是有点'过'了？
|
r*******k
发帖数: 1423 | 8 完全没懂，这个题一定有解么？
遇不到obstacle不拐弯
那一开始s和e不在一条直线，且没obstacle
不就废了？
【在 l******t 的大作中提到】
: 原题如下：
: Given a map which has some obstacles in it. Given a starting point S and
: ending point E, find the shortest path from S to E. Note you can choose
: any(4) direction from S, but during the process, you can only go straight
: from the previous direction, unless you hit an obstacle.
: 看完题目能想到BFS，但是要完全按照题目要求实现有些困惑。求大牛指点啊
: 网上搜索类似问题，甚至涉及到一些算法，包括A*，是不是有点'过'了？
|
p***e
发帖数: 111 | 9 出题的人可能是做ray tracing的，有边界的情况肯定有解。
【在 r*******k 的大作中提到】
: 完全没懂，这个题一定有解么？
: 遇不到obstacle不拐弯
: 那一开始s和e不在一条直线，且没obstacle
: 不就废了？
|
r*******k
发帖数: 1423 | 10 你是说，边界也可以随便乱转?
不过还是没太明白为什么一定有解
另外，这个跟dijkstra应该没啥关系啊
【在 p***e 的大作中提到】
: 出题的人可能是做ray tracing的，有边界的情况肯定有解。
|
|
|
y***n
发帖数: 1594 | 11 For unweighted graph, dijkstra is essentially BFS |
g****r
发帖数: 1589 | 12 这不就是A*吗
【在 l******t 的大作中提到】
: 原题如下：
: Given a map which has some obstacles in it. Given a starting point S and
: ending point E, find the shortest path from S to E. Note you can choose
: any(4) direction from S, but during the process, you can only go straight
: from the previous direction, unless you hit an obstacle.
: 看完题目能想到BFS，但是要完全按照题目要求实现有些困惑。求大牛指点啊
: 网上搜索类似问题，甚至涉及到一些算法，包括A*，是不是有点'过'了？
|
w*****d
发帖数: 105 | 13 我怎么觉得应该用bfs？
用一个队列，将start点先放进去；然后不断pop出一个点，将周围（上下左右）点到
start的距离更新，跳过障碍。同时如果要更新的点距离已经比当前小了，也跳过。被
更新的点再push到队列里。直到队列空，则停止。
最后看看end点的距离是多少。 |
y***n
发帖数: 1594 | 14 Not sure BFS can meet this condition " but during the process, you can only
go straight from the previous direction, unless you hit an obstacle." |
j**********3
发帖数: 3211 | 15 but during the process, you can only go straight
from the previous direction, unless you hit an obstacle. 这啥意思阿？还不带
转弯的？那不是只能走到头了？除非s和e在一条直线，否则碰不上呀！ |
j*****8
发帖数: 3635 | 16 直行，除非碰到障碍才转弯
【在 j**********3 的大作中提到】
: but during the process, you can only go straight
: from the previous direction, unless you hit an obstacle. 这啥意思阿？还不带
: 转弯的？那不是只能走到头了？除非s和e在一条直线，否则碰不上呀！
|
a***n
发帖数: 623 | 17 不能dijkstra吧，原题说“you can only go straight from the previous direction
, unless you hit an obstacle.”，还是BFS。 |
U***A
发帖数: 849 | 18 如果行进的工程中碰到已经搜索过的点，可以转弯吗？ |
c*****n
发帖数: 53 | 19 dijkstra也行，但不能改变时间复杂度，n*m matrix一样是O(n*m)
direction
【在 a***n 的大作中提到】
: 不能dijkstra吧，原题说“you can only go straight from the previous direction
: , unless you hit an obstacle.”，还是BFS。
|
y***n
发帖数: 1594 | 20 讲一讲dijkstra如何保持“you can only go straight from the previous
direction”把. |
c*****n
发帖数: 53 | 21 對每個點求四個方向最近的障礙或撞到邊緣，
再dijk...
【在 y***n 的大作中提到】
: 讲一讲dijkstra如何保持“you can only go straight from the previous
: direction”把.
|
f******4
发帖数: 51 | 22
longway大牛，可否给一个伪代码提示提示啊
【在 l*********8 的大作中提到】
: re
|
