class Main {
public static void getMaxPath(int[][] A){
int rowA = A.length;
int columnA = A[0].length;
int[][] changeA = new int[rowA+1][columnA+1];
int[][] maxA = new int[rowA+1][columnA+1];
for(int i = 0;i < rowA;i++){
for(int j = 0;j < columnA;j++)
changeA[i+1][j+1] = A[i][j];
}
for(int i = 1;i <= rowA;i++){
for(int j = 1; j <= columnA;j++){
if(maxA[i-1][j] >= maxA[i][j-1])
maxA[i][j] = maxA[i-1][j] + changeA[i][j];
else
maxA[i][j] = maxA[i][j-1] + changeA[i][j];
}
}
System.out.println("各个元素位置收集到的最大硬币数:");
for(int i = 1;i <= rowA;i++){
for(int j = 1;j <= columnA;j++)
System.out.print(maxA[i][j]+"\t");
System.out.println();
}
System.out.println("从左上方到右下方收集到最大硬币数的路径(PS:其中元素为-1 表示行走路径):");
maxA[1][1] = 1;
maxA[rowA][columnA] = -1;
int maxI = rowA;
int maxJ = columnA;
while(maxI >= 1 && maxJ >= 1){
if(maxA[maxI][maxJ-1] >= maxA[maxI-1][maxJ]){
maxA[maxI][maxJ-1] = -1;
maxJ = maxJ - 1;
}
else{
maxA[maxI-1][maxJ] = -1;
maxI = maxI - 1;
}
}
for(int i = 1;i <= rowA;i++){
for(int j = 1;j <= columnA;j++)
System.out.print(maxA[i][j]+"\t");
System.out.println();
}
}
public static void main(String[] args){
int[][] A ={{0,0,0,0,1,0},
{0,1,0,1,0,0},
{0,0,0,1,0,1},
{0,0,1,0,0,1},
{1,0,0,0,1,0}};
getMaxPath(A);
}
}