f********e
发帖数: 166 | 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？ | S**I
发帖数: 15689 | 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.
| f********e
发帖数: 166 | 3 能说的具体点么？最短路径的话，node是什么啊？edge是矩阵上的元素，还有上下左右
都能走，怎么表示啊？
【在 S**I 的大作中提到】
: as the description suggested: shortest path
:
: another
| s******n
发帖数: 226 | 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); | f********e
发帖数: 166 | 5 1 1 1 1
5 9 1 1
3 7 4 4
8 2 1 9
从(1,0) 到 （3，2）,上面那个算法就不对了，没考虑向上啊，如果只能向右，向下的
话，就是对的 | s******n
发帖数: 226 | 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）,上面那个算法就不对了，没考虑向上啊，如果只能向右，向下的
: 话，就是对的
| f********e
发帖数: 166 | 7 不好意思啊，不大理解啊，ls能稍微说的具体一点么？矩阵存储vist与否？ | s******n
发帖数: 226 | 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]; | u****t
发帖数: 5 | 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 | P**l
发帖数: 3722 | 10 没说matrix大于0的话，不存在最短的时候，应该返回啥 | | | c****p
发帖数: 6474 | 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 | f*******t
发帖数: 7549 | | e*********l
发帖数: 136 | | f********e
发帖数: 166 | 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])
| s******n
发帖数: 226 | 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;
: }
| f********e
发帖数: 166 | 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角度好理解，好实现
| g*****i
发帖数: 2162 | 17 A*也可以把,可能会快点
【在 e*********l 的大作中提到】
: Dijkstra吧。用普通的优先队列就可以了
| y*******g
发帖数: 6599 | 18 DP？
是说Floyd–Warshall?
复杂度差的比较大吧
样
【在 s******n 的大作中提到】
: 1， 不好意思，在java 的class里，用static variable做全局变量，不需要传参
: 2， 你的意思是说destination不一定是右下角？ 那就传进去就是了 因为不管怎么样
: 都要检测目标那个位置
: BTW： 虽然dijkstra是对的，但是我觉得从DP角度好理解，好实现
| v*****k
发帖数: 7798 | 19 DP记录全部路径后回溯。这就是传说中的Viterbi decoding啊，EE的同学们都知道。 | f********e
发帖数: 166 | 20 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
啊 | | | s******n
发帖数: 226 | 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里。。。咋判断啊？？
: 不知道对不对，嘿嘿，谢谢
:
: 样
| f********e
发帖数: 166 | 22 好吧，大家先歇会，我问的有点BT了，有时间我憋个代码出来，work就行，嘿嘿，谢谢
楼上解答 | y*******g
发帖数: 6599 | 23 但是只有正数环，
有环怎么可能最短？
【在 f********e 的大作中提到】
: 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
: 啊
| s******n
发帖数: 226 | 24 你不是用visit标记过了吗， 不会重复走啊，否则就无限嵌套了
【在 f********e 的大作中提到】
: 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
: 啊
| f********e
发帖数: 166 | 25 如果用matrix track访问过的点，可以避免环,但我想的不是很清楚，脑子爆炸了 | d*******l
发帖数: 338 | 26 我觉得前面那个DP或者叫记忆化搜索的代码是对的。Dijkstra应该也行 | b***e
发帖数: 383 | 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有一个条件就是：顺序。 上层依靠下层，但是下层不能依靠上层。但是，在这
道题里，下层依靠了上层，所以是不行的。 | b******t
发帖数: 965 | 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. 但是，这样做会造成“互相依靠”的情况
| i******s
发帖数: 301 | 29 这种给定范围的search类问题，A*挺好用的，用java也很好实现 | c**********e
发帖数: 2007 | 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 | | | s******n
发帖数: 226 | 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(b
if(c
if(d
return 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+1
down = func(i+1,j,visit);
if(j-1>=0 && !visit[i][j-1])
left = func(i,j-1,visit);
if(j+1
right = 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
| f********e
发帖数: 166 | 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？ | S**I
发帖数: 15689 | 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.
| f********e
发帖数: 166 | 34 能说的具体点么？最短路径的话，node是什么啊？edge是矩阵上的元素，还有上下左右
都能走，怎么表示啊？
【在 S**I 的大作中提到】
: as the description suggested: shortest path
:
: another
| s******n
发帖数: 226 | 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); | f********e
发帖数: 166 | 36 1 1 1 1
5 9 1 1
3 7 4 4
8 2 1 9
从(1,0) 到 （3，2）,上面那个算法就不对了，没考虑向上啊，如果只能向右，向下的
话，就是对的 | s******n
发帖数: 226 | 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）,上面那个算法就不对了，没考虑向上啊，如果只能向右，向下的
: 话，就是对的
| f********e
发帖数: 166 | 38 不好意思啊，不大理解啊，ls能稍微说的具体一点么？矩阵存储vist与否？ | s******n
发帖数: 226 | 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]; | u****t
发帖数: 5 | 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 | | | P**l
发帖数: 3722 | 41 没说matrix大于0的话，不存在最短的时候，应该返回啥 | c****p
发帖数: 6474 | 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 | f*******t
发帖数: 7549 | | e*********l
发帖数: 136 | | f********e
发帖数: 166 | 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])
| s******n
发帖数: 226 | 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;
: }
| f********e
发帖数: 166 | 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角度好理解，好实现
| g*****i
发帖数: 2162 | 48 A*也可以把,可能会快点
【在 e*********l 的大作中提到】
: Dijkstra吧。用普通的优先队列就可以了
| y*******g
发帖数: 6599 | 49 DP？
是说Floyd–Warshall?
复杂度差的比较大吧
样
【在 s******n 的大作中提到】
: 1， 不好意思，在java 的class里，用static variable做全局变量，不需要传参
: 2， 你的意思是说destination不一定是右下角？ 那就传进去就是了 因为不管怎么样
: 都要检测目标那个位置
: BTW： 虽然dijkstra是对的，但是我觉得从DP角度好理解，好实现
| v*****k
发帖数: 7798 | 50 DP记录全部路径后回溯。这就是传说中的Viterbi decoding啊，EE的同学们都知道。 | | | f********e
发帖数: 166 | 51 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
啊 | s******n
发帖数: 226 | 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里。。。咋判断啊？？
: 不知道对不对，嘿嘿，谢谢
:
: 样
| f********e
发帖数: 166 | 53 好吧，大家先歇会，我问的有点BT了，有时间我憋个代码出来，work就行，嘿嘿，谢谢
楼上解答 | y*******g
发帖数: 6599 | 54 但是只有正数环，
有环怎么可能最短？
【在 f********e 的大作中提到】
: 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
: 啊
| s******n
发帖数: 226 | 55 你不是用visit标记过了吗， 不会重复走啊，否则就无限嵌套了
【在 f********e 的大作中提到】
: 这个题，上下左右都能走，可能会有环，如果是用贪婪算法，局部最优不一定全局最优
: 啊
| f********e
发帖数: 166 | 56 如果用matrix track访问过的点，可以避免环,但我想的不是很清楚，脑子爆炸了 | d*******l
发帖数: 338 | 57 我觉得前面那个DP或者叫记忆化搜索的代码是对的。Dijkstra应该也行 | b***e
发帖数: 383 | 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有一个条件就是：顺序。 上层依靠下层，但是下层不能依靠上层。但是，在这
道题里，下层依靠了上层，所以是不行的。 | b******t
发帖数: 965 | 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. 但是，这样做会造成“互相依靠”的情况
| i******s
发帖数: 301 | 60 这种给定范围的search类问题，A*挺好用的，用java也很好实现 | | | c**********e
发帖数: 2007 | 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 | s******n
发帖数: 226 | 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(b
if(c
if(d
return 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+1
down = func(i+1,j,visit);
if(j-1>=0 && !visit[i][j-1])
left = func(i,j-1,visit);
if(j+1
right = 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
| f********e
发帖数: 166 | | n*******w
发帖数: 687 | 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},
|
|
