a*******y
发帖数: 1040 | 1 You have a matrix of size n*n with entries either 1 or 0. 1 means there is a
path, 0 means no path. Find shortest path and print it from (0,0) to (n-1,
n-1)
这个我觉得用backtrack，但是keep那个path有点麻烦，假如你在某一点发现路径走的
cell数目相同，你怎么update那个path？任选一个？ |
f*******n
发帖数: 12623 | |
p*****2
发帖数: 21240 | |
z****e
发帖数: 9 | 4 BFS should be enough because dijgstra is for weighted graph |
p*****2
发帖数: 21240 | 5
嗯。BFS就可以了。
【在 z****e 的大作中提到】
: BFS should be enough because dijgstra is for weighted graph
|
a*******y
发帖数: 1040 | 6 BFS is ok, but printing the path is a bit challenging here since different
path might modify the path, how do you keep the path？
apparently you cannot change the path if the current length is less because
that guy might not reach the end, and might reach the end also.
idea? |
p*****2
发帖数: 21240 | 7
because
backtrack.
【在 a*******y 的大作中提到】
: BFS is ok, but printing the path is a bit challenging here since different
: path might modify the path, how do you keep the path？
: apparently you cannot change the path if the current length is less because
: that guy might not reach the end, and might reach the end also.
: idea?
|
w****x
发帖数: 2483 | 8
DFS也可以吧
【在 p*****2 的大作中提到】
:
: because
: backtrack.
|
p*****2
发帖数: 21240 | 9
当然可以。不过没有BFS优化吧？
【在 w****x 的大作中提到】
:
: DFS也可以吧
|
a*******y
发帖数: 1040 | 10 THIS IS NOT THE POINT!!
why you guys all talk about nosense? DFS BFS all ok. My question was how to
save the path when there are more paths desirable. |
|
|
a*******y
发帖数: 1040 | 11 what I can think of is to create a tree or a trie for the path, add a node
into the tree each time |
p*****2
发帖数: 21240 | 12
to
不是说了backtrack吗？
【在 a*******y 的大作中提到】
: THIS IS NOT THE POINT!!
: why you guys all talk about nosense? DFS BFS all ok. My question was how to
: save the path when there are more paths desirable.
|
a*******y
发帖数: 1040 | 13 how? if you mean recursion, I cannot think of a way to keep this in the
recursion.
【在 p*****2 的大作中提到】
:
: to
: 不是说了backtrack吗？
|
a*******y
发帖数: 1040 | |
f*******n
发帖数: 12623 | 15 Just remember for each node which node it "came from". A dictionary of node
to parent node will work. Then in the end, follow the trail from the finish
to the beginning.
because
【在 a*******y 的大作中提到】
: BFS is ok, but printing the path is a bit challenging here since different
: path might modify the path, how do you keep the path？
: apparently you cannot change the path if the current length is less because
: that guy might not reach the end, and might reach the end also.
: idea?
|
W***n
发帖数: 11530 | 16
a
,
From where to where? Without this info, the question is meaningless.
【在 a*******y 的大作中提到】
: You have a matrix of size n*n with entries either 1 or 0. 1 means there is a
: path, 0 means no path. Find shortest path and print it from (0,0) to (n-1,
: n-1)
: 这个我觉得用backtrack，但是keep那个path有点麻烦，假如你在某一点发现路径走的
: cell数目相同，你怎么update那个path？任选一个？
|
a*******y
发帖数: 1040 | 17 from (0,0) to (n-1, n-1)
【在 W***n 的大作中提到】
:
: a
: ,
: From where to where? Without this info, the question is meaningless.
|
d******a
发帖数: 238 | 18 随手写了一个。
struct point
{
int x;
int y;
};
vector result;
int **visited; //同矩阵同样大小的二维数组，初始化为0
void ShortestPath(int m, int n)
{
vector path;
ShortestPathHelper(0, 0, m, n, path);
for (int i = 0; i < result.size(); i++)
print(result[i]);
}
void ShortestPathHelper(int r, int c, int m, int n, vector
path)
{
static int min = INT_MAX;
if (r == m && c == n)
{
if (path.size() < min)
{
result = path;
min = path.size();
}
return;
}
if (NotValidPoint(r, c))
return;
struct point p = {r, c};
path.push_back(p);
visited[r][c] = 1;
if (visited[r + 1][c] != 1)
ShortestPathHelper(r + 1, c, m, n, path);
if (visited[r][c + 1] != 1)
ShortestPathHelper(r, c + 1, m, n, path);
if (visited[r][c - 1] != 1)
ShortestPathHelper(r, c - 1, m, n, path);
if (visited[r - 1][c] != 1)
ShortestPathHelper(r - 1, c, m, n, path);
visited[r][c] = 0;
} |
a*******y
发帖数: 1040 | 19 no, 你这个不对，
不是shortest的，你要比较下再push
【在 d******a 的大作中提到】
: 随手写了一个。
: struct point
: {
: int x;
: int y;
: };
: vector result;
: int **visited; //同矩阵同样大小的二维数组，初始化为0
: void ShortestPath(int m, int n)
: {
|
d******a
发帖数: 238 | 20 每次递归调用都是拷贝了一次path啊。
【在 a*******y 的大作中提到】
: no, 你这个不对，
: 不是shortest的，你要比较下再push
|
|
|
d******a
发帖数: 238 | 21 我感觉这代码是有些蛮力的，不太好。但result应该是shortest的，因为我是得到了所
有路径，只保存最短的路径。
【在 a*******y 的大作中提到】
: no, 你这个不对，
: 不是shortest的，你要比较下再push
|
a*******y
发帖数: 1040 | 22 你那里只保存最短路劲了？
【在 d******a 的大作中提到】
: 我感觉这代码是有些蛮力的，不太好。但result应该是shortest的，因为我是得到了所
: 有路径，只保存最短的路径。
|
d******a
发帖数: 238 | 23 不好意思，最开始代码忘更新min了。
if (path.size() < min)
{
result = path;
min = path.size(); //这里
}
【在 a*******y 的大作中提到】
: 你那里只保存最短路劲了？
|
a*******y
发帖数: 1040 | 24 你保证你这个step的最短是最后的最短？
【在 d******a 的大作中提到】
: 不好意思，最开始代码忘更新min了。
: if (path.size() < min)
: {
: result = path;
: min = path.size(); //这里
: }
|
i*********7
发帖数: 348 | 25 你可以用指针指向一个vector容器
这样你就不会在每次递归的时候都产生一个新的copy。
而且你用的是dfs，这样就可以保证你产生到达目标点的时候你的中间路径不会因为递
归而改变。
【在 d******a 的大作中提到】
: 我感觉这代码是有些蛮力的，不太好。但result应该是shortest的，因为我是得到了所
: 有路径，只保存最短的路径。
|
i*********7
发帖数: 348 | 26 在C++里，你可以在参数里面用一个vector引用，这样就可以保证每次取到最小路径的
时候都可以保存并且结果最后会在运行完的时候依然保留
在Java你可以用member variable。
to
【在 a*******y 的大作中提到】
: THIS IS NOT THE POINT!!
: why you guys all talk about nosense? DFS BFS all ok. My question was how to
: save the path when there are more paths desirable.
|
c****x
发帖数: 15 | 27 If you want to keep all shortest path, you can modify the hash table in BFS
to allow duplication of cell in search node |
