n*****x
发帖数: 686 | 1 给一个没有边界的2D迷宫，一个起始点，一个终点坐标，以及一个api，bool isPath(
int x, int y)，返回坐标可不可以到达。机器人可以走8个方向。开始是问最短路径，
这还不难。followup是要求K条从起始到终点的不相交路径(K<=8)。
开始我做了一个一条一条找的，面试官不满意，说要同时找到，然后我就懵逼了，估计
跪了。版上哪位大牛给我个思路让我死个明白。。包子送上 |
i*****e
发帖数: 20 | 2 只是思路：
Let a list L be a list of list of cell representing valid non crossing paths
Let a matrix of cells representing the board
Let set S representing cells that have been collected in previous valid path
While L's size is smaller than k
Let set visited representing a set of cells that have been visited
for current bfs path search
Let currentPath representing a list of cells,
For each cell C of board,
visited.put(C)
If C is not in set, dfs(currentPath, visited, C)
visited.remove(C)
bfs(List currentPath, Set visited, Cell C)
//Base condition
If C is end,
add currentPath to L
add all cells of currentPath to S // avoid crossing
return
Let list be a list of cells that can be navigated
For v of each cell of list
If v is not in S,
currentPath.add(v)
visited.add(v)
bfs(currentPath, visited, v)
visited.remove(v)
This shall work. It's not tricky but just tedious. Leetcode middle level. | | |
p**r
发帖数: 5853 | 3 我也打个嘴炮，
终点和起点周围分别对应8个点，
这8个起点，到8个终点之间的路径,说白了就是多叉树，
一条条找就是DFS, 同时找到就是BFS |
b******y
发帖数: 168 | 4 可不可以这么做：
还是最短路径dfs，但是carry两个list，一个是这条路径里所有走过的点，另一个是已
经走完的路径里所有走过的点，每次走一步，update第一个list，同时判断是否与第二
个list有相同元素，有就kill这条路。第二个list一开始是空，每次走完一条路，
update第二个list。 |
R*********4
发帖数: 293 | 5 你其实可以查查 A Star.每个方向走后，你应该保持一个估计值。当你当前走的路的估
计值，超过已保存的路径，则返回到之前估计值最佳的。 |
n*****x
发帖数: 686 | 6 迷宫是没有边界的，没有办法存在matrix里面。。。
paths
path
visited
【在 i*****e 的大作中提到】
: 只是思路：
: Let a list L be a list of list of cell representing valid non crossing paths
: Let a matrix of cells representing the board
: Let set S representing cells that have been collected in previous valid path
: While L's size is smaller than k
: Let set visited representing a set of cells that have been visited
: for current bfs path search
: Let currentPath representing a list of cells,
: For each cell C of board,
: visited.put(C)
|
n*****x
发帖数: 686 | 7 我觉得dfs在这种情况没法用，因为没有边界，所以dfs会停不下来。
用bfs的问题是，在两个点同时能到达某点p的时候，不知道怎么label p
【在 p**r 的大作中提到】
: 我也打个嘴炮，
: 终点和起点周围分别对应8个点，
: 这8个起点，到8个终点之间的路径,说白了就是多叉树，
: 一条条找就是DFS, 同时找到就是BFS
|
n*****x
发帖数: 686 | 8 DFS 貌似连最短路径都求不出来，而且你这么做就不是一起找到了
【在 b******y 的大作中提到】
: 可不可以这么做：
: 还是最短路径dfs，但是carry两个list，一个是这条路径里所有走过的点，另一个是已
: 经走完的路径里所有走过的点，每次走一步，update第一个list，同时判断是否与第二
: 个list有相同元素，有就kill这条路。第二个list一开始是空，每次走完一条路，
: update第二个list。
|
o*******h
发帖数: 64 | 9 bfs是对的思路， 喊出dfs基本挂了。
面试官说同时找出？ 是什么意思？ 怎么个同时法？ |
i*****e
发帖数: 20 | 10 You are right. Maintain a set to maintain those cells visited already. BFS.
When adding next level cells into the queue, only add those that are not
visited already.
Since the board is boarder less. Watch out for stack overflow. It grows very
fast.
: 迷宫是没有边界的，没有办法存在matrix里面。。。
: paths
: path
: visited
【在 n*****x 的大作中提到】
: DFS 貌似连最短路径都求不出来，而且你这么做就不是一起找到了
|
|
|
m****a
发帖数: 604 | 11 迷宫没边界没关系，用战争迷雾。以所在点为坐标，打开半径K的map。update成任何当
前坐标点为圆心半径为k的map，加原来的map |
n*****x
发帖数: 686 | 12 就是说只做一次BFS，就求出所有的路径
我好像有点思路了，用hashmap，对每个坐标点p，要存有几个点能到达p，和p能到达几
个点，每次遇到一个路径就backtrack，选degree of freedom尽量少的点往回走，然后
尽量选非对角的方向（避免相交）。
【在 o*******h 的大作中提到】
: bfs是对的思路， 喊出dfs基本挂了。
: 面试官说同时找出？ 是什么意思？ 怎么个同时法？
|
n*****x
发帖数: 686 | 13 我觉得，要是这题我做出来了，下一个follow up就是怎么scale up了
.
very
【在 i*****e 的大作中提到】
: You are right. Maintain a set to maintain those cells visited already. BFS.
: When adding next level cells into the queue, only add those that are not
: visited already.
: Since the board is boarder less. Watch out for stack overflow. It grows very
: fast.
:
:
: 迷宫是没有边界的，没有办法存在matrix里面。。。
:
: paths
:
: path
:
: visited
|
n*****x
发帖数: 686 | 14 我没说清楚，是离散的integer坐标点，只能走周围的一步，没有到半径这么难。
【在 m****a 的大作中提到】
: 迷宫没边界没关系，用战争迷雾。以所在点为坐标，打开半径K的map。update成任何当
: 前坐标点为圆心半径为k的map，加原来的map
|
d******c
发帖数: 2407 | 15 你说最短路径容易，你是怎么做的？
这题有个api，你可以立刻知道任意两个点有没有路径，但你不知道路径怎么构成，除
非把路径完全构造出来，否则没法知道路径长度。
必须假设你能通过实际走知道是否相通，也就是你能判断A和8个邻居能不能直接走通，
否则连路径都构造不了。那就只能一步步走了。
除了BFS彻底构造路径，没有别的办法吧。无非是借助API能筛掉不连通的点，缩小一些
候选项而已。然后BFS的时候始终维护已知的最短K条路径，更长的不用考虑。
这就是所谓同时找到K条路径。
你不能用任何贪心法，因为贪心法不能保证最短。只能尽量筛掉不合理的，不能去选你
认为更有可能的。上面说A*的也一样不行。 |
n*****x
发帖数: 686 | 16 做一个双向的BFS，维护两个当前到达point set，和一个visited set，和word ladder
类似，第一次相遇就是最短了。
follow up那个，只是说找到所有不相交路径，并没有要求最短。
【在 d******c 的大作中提到】
: 你说最短路径容易，你是怎么做的？
: 这题有个api，你可以立刻知道任意两个点有没有路径，但你不知道路径怎么构成，除
: 非把路径完全构造出来，否则没法知道路径长度。
: 必须假设你能通过实际走知道是否相通，也就是你能判断A和8个邻居能不能直接走通，
: 否则连路径都构造不了。那就只能一步步走了。
: 除了BFS彻底构造路径，没有别的办法吧。无非是借助API能筛掉不连通的点，缩小一些
: 候选项而已。然后BFS的时候始终维护已知的最短K条路径，更长的不用考虑。
: 这就是所谓同时找到K条路径。
: 你不能用任何贪心法，因为贪心法不能保证最短。只能尽量筛掉不合理的，不能去选你
: 认为更有可能的。上面说A*的也一样不行。
|
j*********5
发帖数: 362 | 17 followup中，K个路径也要求是最短么？如果不是，应该K个路线的解法不唯一吧？此外
，如果K=8，但只return了3条路径也行么（其他5条路径走不通） |
n*****x
发帖数: 686 | 18 不要求最短，所以不唯一，但是要求找到最多的，比如只有三条，你就得有三条output
【在 j*********5 的大作中提到】
: followup中，K个路径也要求是最短么？如果不是，应该K个路线的解法不唯一吧？此外
: ，如果K=8，但只return了3条路径也行么（其他5条路径走不通）
|
j*********5
发帖数: 362 | 19 K个点一起走可不可以这样：
终点周围的8个点一起做DFS
1. 每个点先lable出自己可以走的candidate，比如第一个点能走到周围A，B，C三个点
，先不选，但用API确定A、B、C都能连通起点，并且没有被visited；
2. 然后再loop一遍8个点的这些candidate，比如第一个点能走到的ABC中，C也是别人
的candidate，但AB不是，那就走A或B，因为A或B是对于第一个点unique的；后面点比
较吃亏，如果没有unique的就选shared，最后一个点有可能根本没得选（只能走C，但
是C被别的线选了），就算找不到结果了。
3. 八个起点各选一个candidate，然后把八个点变成visited；
4. 基于这些点，重复步骤以上步骤，直到全部到起点或是无路可走？
但这种解法的问题在于会不会选择A或B时没法决策，导致最后的结果可能小于K？ 就是
说，最优解有6条路线可以走通，但只返回了4条。 |
j*********5
发帖数: 362 | 20 明白了，这个的确难，想不通怎么能保证最优解。
output
【在 n*****x 的大作中提到】
: 不要求最短，所以不唯一，但是要求找到最多的，比如只有三条，你就得有三条output
|
j*********5
发帖数: 362 | 21 不好意思，这个解法肯定没法保证最优解。
【在 j*********5 的大作中提到】
: K个点一起走可不可以这样：
: 终点周围的8个点一起做DFS
: 1. 每个点先lable出自己可以走的candidate，比如第一个点能走到周围A，B，C三个点
: ，先不选，但用API确定A、B、C都能连通起点，并且没有被visited；
: 2. 然后再loop一遍8个点的这些candidate，比如第一个点能走到的ABC中，C也是别人
: 的candidate，但AB不是，那就走A或B，因为A或B是对于第一个点unique的；后面点比
: 较吃亏，如果没有unique的就选shared，最后一个点有可能根本没得选（只能走C，但
: 是C被别的线选了），就算找不到结果了。
: 3. 八个起点各选一个candidate，然后把八个点变成visited；
: 4. 基于这些点，重复步骤以上步骤，直到全部到起点或是无路可走？
|
h*********n
发帖数: 11319 | 22 这是哪个公司的题，这么变态？
【在 n*****x 的大作中提到】
: 给一个没有边界的2D迷宫，一个起始点，一个终点坐标，以及一个api，bool isPath(
: int x, int y)，返回坐标可不可以到达。机器人可以走8个方向。开始是问最短路径，
: 这还不难。followup是要求K条从起始到终点的不相交路径(K<=8)。
: 开始我做了一个一条一条找的，面试官不满意，说要同时找到，然后我就懵逼了，估计
: 跪了。版上哪位大牛给我个思路让我死个明白。。包子送上
|
