编辑代码

class Main {

    public static void getMaxPath(int[][] A){
        int rowA = A.length;
        int columnA = A[0].length;         
        //在数组A最上面一行添加一行元素0,在最左边一列添加一列元素0
        int[][] changeA = new int[rowA+1][columnA+1];  //初始化,各个元素均为0
        int[][] maxA = new int[rowA+1][columnA+1];   //用于计算从A[0][0]到达各元素位置收集到的最大硬币数
        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);
    }
}