寻找矩阵的最长路径java
1、创建被查表，计算最优路径
2、路径选择和输出：
3、主要测试函数
4、源代码：
package ch3.dynamic.algorithm;
public class CowSolitaire {
public static int cowS(int[][] A) {
// object [][] array ;
// array.length 行数
// array [0].length 列数
int rows = A.length;
int[][] f = new int[rows + 1][rows + 1];
int i, j, k;
for (i = 0; i < rows + 1; i++) {
f[i][0] = 0;
}
for (j = 1; j < rows + 1; j++) {
f[rows][j] = 0;
}
int q = 0;
for (i = rows - 1; i >= 0; i--) {
for (j = 1; j <= rows; j++) {
if (f[i + 1][j] > f[i][j - 1]) { // /将左边和下边的最优路径进行比较选择
q = f[i + 1][j];
} else {
q = f[i][j - 1];
}
f[i][j] = A[i][j - 1] + q; // /这个地方要注意安排i,j的符号
}
}
/**
***/
Pair[] path = new Pair[7];
int count = 0;
path[count] = Pair.make(4, 1);
count = count + 1;
i = 3;
j = 1;
while (i >= 0 && j <= 4 && count < 7) {
if (i == 0 && j == 4) {
path[count] = Pair.make(1, 4);
i--;
j++;
} else if (i == 0) {
path[count] = Pair.make(i + 1, j + 1);
} else if (j == 4) {
path[count] = Pair.make(i, j);
} else if (f[i - 1][j] > f[i][j + 1]) { // /将左边和下边的最优路径进行比较选择
path[count] = Pair.make(i, j);
i = i - 1;
} else {
path[count] = Pair.make(i + 1, j + 1);
j = j + 1;
}
count++;
}
// path[count]=Pair.make(1, 4);
for (int ii = 0; ii < path.length; ii++) {
System.out.println("THE " + ii + " STEP: 【" + path[ii].first
+ " , " + path[ii].second + "】");
}
return f[0][rows];
}
/***
* 整理一下这个地方如果读文件需要使用的思路 如果从文件中读出来 首先是读出第一行，获取值，初始化一个矩阵 将文档内容分行读出，按照空格分离
* 根据switch实现字符转化为数据（int） 构建一个整型的矩阵 实现遍历找到到达每一个位置的左右路径解
* */
public static void main(String[] args) {
int[][] A = { { 8, 1, 3, 1 }, { 8, 4, 12, 12 }, { 5, 9, 13, 7 },
{ 10, 12, 1, 2 } };
// System.out.println(A.length);
int res = cowS(A);
System.out.println("===最长路径是===");
System.out.println("RESULT:" + res);
}
}
5、运行结果：
