logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
再问个Amazon面试题
avatar
再问个Amazon面试题# JobHunting - 待字闺中
f*e
1 楼
Given a matrix you have to find the shortest path from one point to another
within the matrix. The cost of path is all the matrix entries on the way.
You can move in any direction (up, down, left, right, diagonally)
e.g.
5 9 10 1
3 7 4 4
8 2 1 9
比如要从（0,0）到（2，2）
路径是(0,0)->(1,0)->(2,1)->(2,2)
cost: 5+3+2+1 = 11.
这个题是DP？贪婪算法？还是NP？
avatar
S*I
2 楼
as the description suggested: shortest path

another

【在 f********e 的大作中提到】
: Given a matrix you have to find the shortest path from one point to another
: within the matrix. The cost of path is all the matrix entries on the way.
: You can move in any direction (up, down, left, right, diagonally)
: e.g.
: 5 9 10 1
: 3 7 4 4
: 8 2 1 9
: 比如要从（0,0）到（2，2）
: 路径是(0,0)->(1,0)->(2,1)->(2,2)
: cost: 5+3+2+1 = 11.
avatar
f*e
3 楼
能说的具体点么？最短路径的话，node是什么啊？edge是矩阵上的元素，还有上下左右
都能走，怎么表示啊？

【在 S**I 的大作中提到】
: as the description suggested: shortest path
:
: another
avatar
s*n
4 楼
Func(index a, index b){
If( path[a,b]!= -1) return path[a,b]
If a>b
Return ms value
If a==b
Renturn w(a)
Else return min(function(a.right,b), function(a.down,b))+w(a);
avatar
f*e
5 楼
1 1 1 1
5 9 1 1
3 7 4 4
8 2 1 9
从(1,0) 到 （3，2）,上面那个算法就不对了，没考虑向上啊，如果只能向右，向下的
话，就是对的
avatar
s*n
6 楼
那就min 4周的 同时用一个矩阵储存visit与否，用传值，每次不影响别的判断

【在 f********e 的大作中提到】
: 1 1 1 1
: 5 9 1 1
: 3 7 4 4
: 8 2 1 9
: 从(1,0) 到 （3，2）,上面那个算法就不对了，没考虑向上啊，如果只能向右，向下的
: 话，就是对的
avatar
f*e
7 楼
不好意思啊，不大理解啊，ls能稍微说的具体一点么？矩阵存储vist与否？
avatar
s*n
8 楼
Func(int i, int j, boolean[][] visit){
If( path[i][j]!= -1) return path[a,b];
If( i>m || j>n || i<0 || j<0){
return Integer.MAX_VALUE;
}
If(i==m-1 && j == n-1)
return w[i][j];
visit[i][j] =true;
int up,down,left,right = Integer.MAX_VALUE;
if(!visit[i-1][j])
up = func(i-1,j,visit);
if(!visit[i+1][j])
down = func(i+1,j,visit);
if(!visit[i][j-1])
left = func(i,j-1,visit);
if(!visit[i-1][j])
right = func(i-1,j,visit);
visit[i][j]=false;
path[i][j] = min(up,down,left,right)+w(a);
return path[i][j];
avatar
u*t
9 楼
可以考虑用Dijkstra，把Matrix转化成一个图
比如Matrix中4个位置
a b
c d
值分别是
1 2
3 4
可以转化为图
a - b
| \/ |
c - d
边的权重是对应cell的值相加，例如
(a, b) = 3
(a, c) = 4
(a, d) = 5
avatar
P*l
10 楼
没说matrix大于0的话，不存在最短的时候，应该返回啥
avatar
c*p
11 楼
单源最短路径，算法都是现成的，
网上搜一下就得了。
理解成DP也可以：
min_distance(starting, ending) = min(
starting.up + min_distance(starting.up, ending),
starting.down + min_distance(starting.down, ending),
starting.left + min_distance(starting.left, ending),
starting.right + min_distance(starting.right, ending))【 在
fourinlove (4inlove) 的大作中提到: 】
another
avatar
f*t
12 楼
就是Dijkstra吧，BFS
avatar
e*l
13 楼
Dijkstra吧。用普通的优先队列就可以了
avatar
f*e
14 楼
我觉得你的代码有点问题，path应该也传参吧，其次，base case有上下左右四个位置
临近目标位置,不该只是 i==m-1&&j==n-1吧
还有，题目这样做，是简化了路径，只有上下左右走了，不走对角线
if((i==m-1&&j==n)||(i==m+1&&j==n)||(i==m&&j==n-1)||(i==m&&j==n+1))
{
path.add(i,j);
visit(i,j)=true;
return;
}

【在 s******n 的大作中提到】
: Func(int i, int j, boolean[][] visit){
: If( path[i][j]!= -1) return path[a,b];
: If( i>m || j>n || i<0 || j<0){
: return Integer.MAX_VALUE;
: }
: If(i==m-1 && j == n-1)
: return w[i][j];
: visit[i][j] =true;
: int up,down,left,right = Integer.MAX_VALUE;
: if(!visit[i-1][j])
avatar
s*n
15 楼
1， 不好意思，在java 的class里，用static variable做全局变量，不需要传参
2， 你的意思是说destination不一定是右下角？ 那就传进去就是了 因为不管怎么样
都要检测目标那个位置
BTW： 虽然dijkstra是对的，但是我觉得从DP角度好理解，好实现

【在 f********e 的大作中提到】
: 我觉得你的代码有点问题，path应该也传参吧，其次，base case有上下左右四个位置
: 临近目标位置,不该只是 i==m-1&&j==n-1吧
: 还有，题目这样做，是简化了路径，只有上下左右走了，不走对角线
: if((i==m-1&&j==n)||(i==m+1&&j==n)||(i==m&&j==n-1)||(i==m&&j==n+1))
: {
: path.add(i,j);
: visit(i,j)=true;
: return;
: }
avatar
f*e
16 楼
1.visit那个矩阵是不是必须当参数，不能当static变量？
2.destination不一定是右下角,应该传参，我不太清楚的是base case，我觉得是
destination上下左右四个位置，直接返回，加到path里，mark visit,而不是只是
destination 的左上角的位置
不对。。，应该是那个选为min的加到path里。。。咋判断啊？？
不知道对不对，嘿嘿，谢谢

样

【在 s******n 的大作中提到】
: 1， 不好意思，在java 的class里，用static variable做全局变量，不需要传参
: 2， 你的意思是说destination不一定是右下角？ 那就传进去就是了 因为不管怎么样
: 都要检测目标那个位置
: BTW： 虽然dijkstra是对的，但是我觉得从DP角度好理解，好实现
avatar
g*i
17 楼
A*也可以把,可能会快点

【在 e*********l 的大作中提到】
: Dijkstra吧。用普通的优先队列就可以了
avatar
y*g
18 楼
DP？
是说Floyd–Warshall?
复杂度差的比较大吧

样

【在 s******n 的大作中提到】
: 1， 不好意思，在java 的class里，用static variable做全局变量，不需要传参
: 2， 你的意思是说destination不一定是右下角？ 那就传进去就是了 因为不管怎么样
: 都要检测目标那个位置
: BTW： 虽然dijkstra是对的，但是我觉得从DP角度好理解，好实现
avatar
v*k
19 楼
DP记录全部路径后回溯。这就是传说中的Viterbi decoding啊，EE的同学们都知道。
avatar
f*e
20 楼
这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
啊
avatar
s*n
21 楼
1, 我觉得可以
2， 对一个destination 要建一个matrix，ai~ 累啊
3， 我还是觉得要走到dest的位置上
4，我的path存计算的最短路径值，具体的要book keeping 一下

【在 f********e 的大作中提到】
: 1.visit那个矩阵是不是必须当参数，不能当static变量？
: 2.destination不一定是右下角,应该传参，我不太清楚的是base case，我觉得是
: destination上下左右四个位置，直接返回，加到path里，mark visit,而不是只是
: destination 的左上角的位置
: 不对。。，应该是那个选为min的加到path里。。。咋判断啊？？
: 不知道对不对，嘿嘿，谢谢
:
: 样
avatar
f*e
22 楼
好吧，大家先歇会，我问的有点BT了，有时间我憋个代码出来，work就行，嘿嘿，谢谢
楼上解答
avatar
y*g
23 楼
但是只有正数环，
有环怎么可能最短？

【在 f********e 的大作中提到】
: 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
: 啊
avatar
s*n
24 楼
你不是用visit标记过了吗， 不会重复走啊，否则就无限嵌套了

【在 f********e 的大作中提到】
: 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
: 啊
avatar
f*e
25 楼
如果用matrix track访问过的点，可以避免环,但我想的不是很清楚，脑子爆炸了
avatar
d*l
26 楼
我觉得前面那个DP或者叫记忆化搜索的代码是对的。Dijkstra应该也行
avatar
b*e
27 楼
我认为用DP是不行的。原因是对于一个给定的点，要找出它到原始点的最短距离，就要
比较这个点周围所有点（总共8个）到原始点的最短距离+周围点的值。比如：
1 1 1 1
2 2 2 1
3 3 3 1
4 4 4 1
5 5 1 1
我们用MD（i,j）表示这个点到（0,0）点的最短距离，如果要找到点（3,1）到点（0,0
）的最短距离，就要找到min{MD(2,0)+3, MD(2,1)+3, MD(2,2)+3, MD(3,0)+4, MD(3,
2)+4, MD(4,0)+5, MD(4,1)+5, MD(4,2)+1} + 4. 但是，这样做会造成“互相依靠”的情况
。
利用DP有一个条件就是：顺序。 上层依靠下层，但是下层不能依靠上层。但是，在这
道题里，下层依靠了上层，所以是不行的。
avatar
b*t
28 楼
没有负的边 all pairs shortest path就是DP
只是复杂性大一点而已

,0
的情况

【在 b***e 的大作中提到】
: 我认为用DP是不行的。原因是对于一个给定的点，要找出它到原始点的最短距离，就要
: 比较这个点周围所有点（总共8个）到原始点的最短距离+周围点的值。比如：
: 1 1 1 1
: 2 2 2 1
: 3 3 3 1
: 4 4 4 1
: 5 5 1 1
: 我们用MD（i,j）表示这个点到（0,0）点的最短距离，如果要找到点（3,1）到点（0,0
: ）的最短距离，就要找到min{MD(2,0)+3, MD(2,1)+3, MD(2,2)+3, MD(3,0)+4, MD(3,
: 2)+4, MD(4,0)+5, MD(4,1)+5, MD(4,2)+1} + 4. 但是，这样做会造成“互相依靠”的情况
avatar
i*s
29 楼
这种给定范围的search类问题，A*挺好用的，用java也很好实现
avatar
c*e
30 楼
Check if it works for the following: X -> Y
100 1 1 1 1 100
100 1 100 100 100 X
1 100 100 Y 100 100
1 100 100 100 1 100
1 1 1 1 100 100
avatar
s*n
31 楼
假设x = 1， Y=1
输出 202.
import java.util.*;
class Short{
public static int[][] path;
public static boolean [][]visit;
public static int ii;
public static int jj;
public static int[][]w = { {100, 1, 1, 1, 1, 100},
{100, 1, 100, 100, 100, 1},
{1, 100, 100, 1, 100, 100},
{1, 100, 100, 100, 1, 100},
{1, 1, 1, 1, 100, 100}
};
static int m =5;
static int n =6;


static int min(int a, int b, int c, int d){
int min = a;
if(bif(cif(dreturn min;


}

static int func(int i, int j, boolean[][] visit){

if( i>m || j>n || i<0 || j<0){
return Integer.MAX_VALUE;
}
if( path[i][j]!= -1) return path[i][j];
if(i==ii && j == jj)
return w[i][j];
visit[i][j] =true;
int up= Integer.MAX_VALUE;
int down= Integer.MAX_VALUE;
int left= Integer.MAX_VALUE;
int right = Integer.MAX_VALUE;
if(i-1>=0 && !visit[i-1][j])
up = func(i-1,j,visit);
if(i+1down = func(i+1,j,visit);
if(j-1>=0 && !visit[i][j-1])
left = func(i,j-1,visit);
if(j+1right = func(i-1,j,visit);
visit[i][j]=false;
int cur_min = min(up,down,left,right);
if(cur_min == Integer.MAX_VALUE)
path[i][j] = cur_min;
else path[i][j] = cur_min+w[i][j];
return path[i][j];
}

public static void main(String[] args){
// w = new int[5][6];
ii =2;
jj =3;
visit = new boolean [5][6];
for(int i=0;i<5;i++)
for(int j=0;j<6;j++)
visit[i][j] = false;
path = new int[5][6];
for(int i=0;i<5;i++)
for(int j=0;j<6;j++)
path[i][j] = -1;

System.out.println(func(1,5,visit));
}




}

【在 c**********e 的大作中提到】
: Check if it works for the following: X -> Y
: 100 1 1 1 1 100
: 100 1 100 100 100 X
: 1 100 100 Y 100 100
: 1 100 100 100 1 100
: 1 1 1 1 100 100
avatar
f*e
32 楼
Given a matrix you have to find the shortest path from one point to another
within the matrix. The cost of path is all the matrix entries on the way.
You can move in any direction (up, down, left, right, diagonally)
e.g.
5 9 10 1
3 7 4 4
8 2 1 9
比如要从（0,0）到（2，2）
路径是(0,0)->(1,0)->(2,1)->(2,2)
cost: 5+3+2+1 = 11.
这个题是DP？贪婪算法？还是NP？
avatar
S*I
33 楼
as the description suggested: shortest path

another

【在 f********e 的大作中提到】
: Given a matrix you have to find the shortest path from one point to another
: within the matrix. The cost of path is all the matrix entries on the way.
: You can move in any direction (up, down, left, right, diagonally)
: e.g.
: 5 9 10 1
: 3 7 4 4
: 8 2 1 9
: 比如要从（0,0）到（2，2）
: 路径是(0,0)->(1,0)->(2,1)->(2,2)
: cost: 5+3+2+1 = 11.
avatar
f*e
34 楼
能说的具体点么？最短路径的话，node是什么啊？edge是矩阵上的元素，还有上下左右
都能走，怎么表示啊？

【在 S**I 的大作中提到】
: as the description suggested: shortest path
:
: another
avatar
s*n
35 楼
Func(index a, index b){
If( path[a,b]!= -1) return path[a,b]
If a>b
Return ms value
If a==b
Renturn w(a)
Else return min(function(a.right,b), function(a.down,b))+w(a);
avatar
f*e
36 楼
1 1 1 1
5 9 1 1
3 7 4 4
8 2 1 9
从(1,0) 到 （3，2）,上面那个算法就不对了，没考虑向上啊，如果只能向右，向下的
话，就是对的
avatar
s*n
37 楼
那就min 4周的 同时用一个矩阵储存visit与否，用传值，每次不影响别的判断

【在 f********e 的大作中提到】
: 1 1 1 1
: 5 9 1 1
: 3 7 4 4
: 8 2 1 9
: 从(1,0) 到 （3，2）,上面那个算法就不对了，没考虑向上啊，如果只能向右，向下的
: 话，就是对的
avatar
f*e
38 楼
不好意思啊，不大理解啊，ls能稍微说的具体一点么？矩阵存储vist与否？
avatar
s*n
39 楼
Func(int i, int j, boolean[][] visit){
If( path[i][j]!= -1) return path[a,b];
If( i>m || j>n || i<0 || j<0){
return Integer.MAX_VALUE;
}
If(i==m-1 && j == n-1)
return w[i][j];
visit[i][j] =true;
int up,down,left,right = Integer.MAX_VALUE;
if(!visit[i-1][j])
up = func(i-1,j,visit);
if(!visit[i+1][j])
down = func(i+1,j,visit);
if(!visit[i][j-1])
left = func(i,j-1,visit);
if(!visit[i-1][j])
right = func(i-1,j,visit);
visit[i][j]=false;
path[i][j] = min(up,down,left,right)+w(a);
return path[i][j];
avatar
u*t
40 楼
可以考虑用Dijkstra，把Matrix转化成一个图
比如Matrix中4个位置
a b
c d
值分别是
1 2
3 4
可以转化为图
a - b
| \/ |
c - d
边的权重是对应cell的值相加，例如
(a, b) = 3
(a, c) = 4
(a, d) = 5
avatar
P*l
41 楼
没说matrix大于0的话，不存在最短的时候，应该返回啥
avatar
c*p
42 楼
单源最短路径，算法都是现成的，
网上搜一下就得了。
理解成DP也可以：
min_distance(starting, ending) = min(
starting.up + min_distance(starting.up, ending),
starting.down + min_distance(starting.down, ending),
starting.left + min_distance(starting.left, ending),
starting.right + min_distance(starting.right, ending))【 在
fourinlove (4inlove) 的大作中提到: 】
another
avatar
f*t
43 楼
就是Dijkstra吧，BFS
avatar
e*l
44 楼
Dijkstra吧。用普通的优先队列就可以了
avatar
f*e
45 楼
我觉得你的代码有点问题，path应该也传参吧，其次，base case有上下左右四个位置
临近目标位置,不该只是 i==m-1&&j==n-1吧
还有，题目这样做，是简化了路径，只有上下左右走了，不走对角线
if((i==m-1&&j==n)||(i==m+1&&j==n)||(i==m&&j==n-1)||(i==m&&j==n+1))
{
path.add(i,j);
visit(i,j)=true;
return;
}

【在 s******n 的大作中提到】
: Func(int i, int j, boolean[][] visit){
: If( path[i][j]!= -1) return path[a,b];
: If( i>m || j>n || i<0 || j<0){
: return Integer.MAX_VALUE;
: }
: If(i==m-1 && j == n-1)
: return w[i][j];
: visit[i][j] =true;
: int up,down,left,right = Integer.MAX_VALUE;
: if(!visit[i-1][j])
avatar
s*n
46 楼
1， 不好意思，在java 的class里，用static variable做全局变量，不需要传参
2， 你的意思是说destination不一定是右下角？ 那就传进去就是了 因为不管怎么样
都要检测目标那个位置
BTW： 虽然dijkstra是对的，但是我觉得从DP角度好理解，好实现

【在 f********e 的大作中提到】
: 我觉得你的代码有点问题，path应该也传参吧，其次，base case有上下左右四个位置
: 临近目标位置,不该只是 i==m-1&&j==n-1吧
: 还有，题目这样做，是简化了路径，只有上下左右走了，不走对角线
: if((i==m-1&&j==n)||(i==m+1&&j==n)||(i==m&&j==n-1)||(i==m&&j==n+1))
: {
: path.add(i,j);
: visit(i,j)=true;
: return;
: }
avatar
f*e
47 楼
1.visit那个矩阵是不是必须当参数，不能当static变量？
2.destination不一定是右下角,应该传参，我不太清楚的是base case，我觉得是
destination上下左右四个位置，直接返回，加到path里，mark visit,而不是只是
destination 的左上角的位置
不对。。，应该是那个选为min的加到path里。。。咋判断啊？？
不知道对不对，嘿嘿，谢谢

样

【在 s******n 的大作中提到】
: 1， 不好意思，在java 的class里，用static variable做全局变量，不需要传参
: 2， 你的意思是说destination不一定是右下角？ 那就传进去就是了 因为不管怎么样
: 都要检测目标那个位置
: BTW： 虽然dijkstra是对的，但是我觉得从DP角度好理解，好实现
avatar
g*i
48 楼
A*也可以把,可能会快点

【在 e*********l 的大作中提到】
: Dijkstra吧。用普通的优先队列就可以了
avatar
y*g
49 楼
DP？
是说Floyd–Warshall?
复杂度差的比较大吧

样

【在 s******n 的大作中提到】
: 1， 不好意思，在java 的class里，用static variable做全局变量，不需要传参
: 2， 你的意思是说destination不一定是右下角？ 那就传进去就是了 因为不管怎么样
: 都要检测目标那个位置
: BTW： 虽然dijkstra是对的，但是我觉得从DP角度好理解，好实现
avatar
v*k
50 楼
DP记录全部路径后回溯。这就是传说中的Viterbi decoding啊，EE的同学们都知道。
avatar
f*e
51 楼
这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
啊
avatar
s*n
52 楼
1, 我觉得可以
2， 对一个destination 要建一个matrix，ai~ 累啊
3， 我还是觉得要走到dest的位置上
4，我的path存计算的最短路径值，具体的要book keeping 一下

【在 f********e 的大作中提到】
: 1.visit那个矩阵是不是必须当参数，不能当static变量？
: 2.destination不一定是右下角,应该传参，我不太清楚的是base case，我觉得是
: destination上下左右四个位置，直接返回，加到path里，mark visit,而不是只是
: destination 的左上角的位置
: 不对。。，应该是那个选为min的加到path里。。。咋判断啊？？
: 不知道对不对，嘿嘿，谢谢
:
: 样
avatar
f*e
53 楼
好吧，大家先歇会，我问的有点BT了，有时间我憋个代码出来，work就行，嘿嘿，谢谢
楼上解答
avatar
y*g
54 楼
但是只有正数环，
有环怎么可能最短？

【在 f********e 的大作中提到】
: 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
: 啊
avatar
s*n
55 楼
你不是用visit标记过了吗， 不会重复走啊，否则就无限嵌套了

【在 f********e 的大作中提到】
: 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
: 啊
avatar
f*e
56 楼
如果用matrix track访问过的点，可以避免环,但我想的不是很清楚，脑子爆炸了
avatar
d*l
57 楼
我觉得前面那个DP或者叫记忆化搜索的代码是对的。Dijkstra应该也行
avatar
b*e
58 楼
我认为用DP是不行的。原因是对于一个给定的点，要找出它到原始点的最短距离，就要
比较这个点周围所有点（总共8个）到原始点的最短距离+周围点的值。比如：
1 1 1 1
2 2 2 1
3 3 3 1
4 4 4 1
5 5 1 1
我们用MD（i,j）表示这个点到（0,0）点的最短距离，如果要找到点（3,1）到点（0,0
）的最短距离，就要找到min{MD(2,0)+3, MD(2,1)+3, MD(2,2)+3, MD(3,0)+4, MD(3,
2)+4, MD(4,0)+5, MD(4,1)+5, MD(4,2)+1} + 4. 但是，这样做会造成“互相依靠”的情况
。
利用DP有一个条件就是：顺序。 上层依靠下层，但是下层不能依靠上层。但是，在这
道题里，下层依靠了上层，所以是不行的。
avatar
b*t
59 楼
没有负的边 all pairs shortest path就是DP
只是复杂性大一点而已

,0
的情况

【在 b***e 的大作中提到】
: 我认为用DP是不行的。原因是对于一个给定的点，要找出它到原始点的最短距离，就要
: 比较这个点周围所有点（总共8个）到原始点的最短距离+周围点的值。比如：
: 1 1 1 1
: 2 2 2 1
: 3 3 3 1
: 4 4 4 1
: 5 5 1 1
: 我们用MD（i,j）表示这个点到（0,0）点的最短距离，如果要找到点（3,1）到点（0,0
: ）的最短距离，就要找到min{MD(2,0)+3, MD(2,1)+3, MD(2,2)+3, MD(3,0)+4, MD(3,
: 2)+4, MD(4,0)+5, MD(4,1)+5, MD(4,2)+1} + 4. 但是，这样做会造成“互相依靠”的情况
avatar
i*s
60 楼
这种给定范围的search类问题，A*挺好用的，用java也很好实现
avatar
c*e
61 楼
Check if it works for the following: X -> Y
100 1 1 1 1 100
100 1 100 100 100 X
1 100 100 Y 100 100
1 100 100 100 1 100
1 1 1 1 100 100
avatar
s*n
62 楼
假设x = 1， Y=1
输出 202.
import java.util.*;
class Short{
public static int[][] path;
public static boolean [][]visit;
public static int ii;
public static int jj;
public static int[][]w = { {100, 1, 1, 1, 1, 100},
{100, 1, 100, 100, 100, 1},
{1, 100, 100, 1, 100, 100},
{1, 100, 100, 100, 1, 100},
{1, 1, 1, 1, 100, 100}
};
static int m =5;
static int n =6;


static int min(int a, int b, int c, int d){
int min = a;
if(bif(cif(dreturn min;


}

static int func(int i, int j, boolean[][] visit){

if( i>m || j>n || i<0 || j<0){
return Integer.MAX_VALUE;
}
if( path[i][j]!= -1) return path[i][j];
if(i==ii && j == jj)
return w[i][j];
visit[i][j] =true;
int up= Integer.MAX_VALUE;
int down= Integer.MAX_VALUE;
int left= Integer.MAX_VALUE;
int right = Integer.MAX_VALUE;
if(i-1>=0 && !visit[i-1][j])
up = func(i-1,j,visit);
if(i+1down = func(i+1,j,visit);
if(j-1>=0 && !visit[i][j-1])
left = func(i,j-1,visit);
if(j+1right = func(i-1,j,visit);
visit[i][j]=false;
int cur_min = min(up,down,left,right);
if(cur_min == Integer.MAX_VALUE)
path[i][j] = cur_min;
else path[i][j] = cur_min+w[i][j];
return path[i][j];
}

public static void main(String[] args){
// w = new int[5][6];
ii =2;
jj =3;
visit = new boolean [5][6];
for(int i=0;i<5;i++)
for(int j=0;j<6;j++)
visit[i][j] = false;
path = new int[5][6];
for(int i=0;i<5;i++)
for(int j=0;j<6;j++)
path[i][j] = -1;

System.out.println(func(1,5,visit));
}




}

【在 c**********e 的大作中提到】
: Check if it works for the following: X -> Y
: 100 1 1 1 1 100
: 100 1 100 100 100 X
: 1 100 100 Y 100 100
: 1 100 100 100 1 100
: 1 1 1 1 100 100
avatar
f*e
63 楼
赞shinrain !
avatar
n*w
64 楼
这个复杂度多少?
其实写个循环就能解决上下层dependent的关系。每一次循环都相当于dp一次。伪码如
下。
modified = true；
while(modified){
modified = false；
从start point开始由内向外一圈一圈计算每个节点的最小cost。每个节点要考虑8
个方向的相邻节点。如果有更短路径，modified设为true，更新cost。
}
dependent的原因是因为下一层如果有更短的路径了，上一层不知道下一层的结果。
但是在下一个循环的时候上层可以得到下层的计算结果。

【在 s******n 的大作中提到】
: 假设x = 1， Y=1
: 输出 202.
: import java.util.*;
: class Short{
: public static int[][] path;
: public static boolean [][]visit;
: public static int ii;
: public static int jj;
: public static int[][]w = { {100, 1, 1, 1, 1, 100},
: {100, 1, 100, 100, 100, 1},
相关阅读
关于美国onsite的签证面试问到看过的题目，大家都怎么回答？有人面试过 trident microsystem 么？用多线程怎么比单线程还慢呢？ (转载)种族，性别信息大家怎么写的？Amazon 面经公司这样答复到底是是还是不是？？现在转行读CS有前途吗？请教从HR到第二轮technical screen要等多久请问这个prepaidlegal.com是什么公司阿？跳槽心得【JOBS】招多个Software Engineer and QA at San Franciscoactive clearance是不是只有citizen才能有？Offer到，没包子发，发发面经~~有人TAKE 过BLACKROCK的JAVA TEST吗？ (转载)急求refer：找supply chain, buyer, purchasing, finance/accoun怎样延签offer? 谁有经验或者建议你们OPT都等了多久啊？求教一个猎头的email这种情况怎么往简历上面加？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。