logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
shortest path in matrix
avatar
shortest path in matrix# JobHunting - 待字闺中
a*y
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？任选一个？
avatar
f*n
2 楼
BFS?
avatar
p*2
3 楼
dijgstra就可以了吧？
avatar
z*e
4 楼
BFS should be enough because dijgstra is for weighted graph
avatar
p*2
5 楼

嗯。BFS就可以了。

【在 z****e 的大作中提到】
: BFS should be enough because dijgstra is for weighted graph
avatar
a*y
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?
avatar
p*2
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?
avatar
w*x
8 楼

DFS也可以吧

【在 p*****2 的大作中提到】
:
: because
: backtrack.
avatar
p*2
9 楼

当然可以。不过没有BFS优化吧？

【在 w****x 的大作中提到】
:
: DFS也可以吧
avatar
a*y
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.
avatar
a*y
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
avatar
p*2
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.
avatar
a*y
13 楼
how? if you mean recursion, I cannot think of a way to keep this in the
recursion.

【在 p*****2 的大作中提到】
:
: to
: 不是说了backtrack吗？
avatar
a*y
14 楼
谁来个贴个code?
avatar
f*n
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?
avatar
W*n
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？任选一个？
avatar
a*y
17 楼
from (0,0) to (n-1, n-1)

【在 W***n 的大作中提到】
:
: a
: ,
: From where to where? Without this info, the question is meaningless.
avatar
d*a
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;
}
avatar
a*y
19 楼
no, 你这个不对，
不是shortest的，你要比较下再push

【在 d******a 的大作中提到】
: 随手写了一个。
: struct point
: {
: int x;
: int y;
: };
: vector result;
: int **visited; //同矩阵同样大小的二维数组，初始化为0
: void ShortestPath(int m, int n)
: {
avatar
d*a
20 楼
每次递归调用都是拷贝了一次path啊。

【在 a*******y 的大作中提到】
: no, 你这个不对，
: 不是shortest的，你要比较下再push
avatar
d*a
21 楼
我感觉这代码是有些蛮力的，不太好。但result应该是shortest的，因为我是得到了所
有路径，只保存最短的路径。

【在 a*******y 的大作中提到】
: no, 你这个不对，
: 不是shortest的，你要比较下再push
avatar
a*y
22 楼
你那里只保存最短路劲了？

【在 d******a 的大作中提到】
: 我感觉这代码是有些蛮力的，不太好。但result应该是shortest的，因为我是得到了所
: 有路径，只保存最短的路径。
avatar
d*a
23 楼
不好意思，最开始代码忘更新min了。
if (path.size() < min)
{
result = path;
min = path.size(); //这里
}

【在 a*******y 的大作中提到】
: 你那里只保存最短路劲了？
avatar
a*y
24 楼
你保证你这个step的最短是最后的最短？

【在 d******a 的大作中提到】
: 不好意思，最开始代码忘更新min了。
: if (path.size() < min)
: {
: result = path;
: min = path.size(); //这里
: }
avatar
i*7
25 楼
你可以用指针指向一个vector容器
这样你就不会在每次递归的时候都产生一个新的copy。
而且你用的是dfs，这样就可以保证你产生到达目标点的时候你的中间路径不会因为递
归而改变。

【在 d******a 的大作中提到】
: 我感觉这代码是有些蛮力的，不太好。但result应该是shortest的，因为我是得到了所
: 有路径，只保存最短的路径。
avatar
i*7
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.
avatar
c*x
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
相关阅读
请问OPT找学校老师挂靠的问题，多谢！contact job 问题求助昨天面试，今早收到offer!请推荐一个好的猎头网站QUALCOMM一题OPT批准之后是不是立刻有邮件通知？跟面试的打电话直打磕巴，怎么办接到一个理想公司的电面机会，但是不是合适的职位，大家会怎么办？ONSITE后的绝望再求裸奔经验!问一道题(2)iterative string permutation[bssd]人生圆满了，跟猎头公司的人argue了真想去死，猪头猪脑上次的博彩咋地咧？FW: Opportunity in ASIC design at Juniper Networks都要写感谢信吗h1b date of issue 按哪天算有什么技巧能顺利通过behavioral assessment么？急问OPT加急回复
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。