编辑代码

import java.util.Arrays; 
import java.util.LinkedList; 
 
public class Main {
    // 定义测试用例
	public static void main(String[] args) { 
		int[][] coin1 = { 
			{1,0,0,0,1,0}, 
		    {1,0,0,0,1,1},  
			{0,0,0,1,0,1}, 
			{0,0,1,0,0,1}, 
			{1,0,0,0,1,0} 
		}; 
		LinkedList<String> p1 = new LinkedList<String>(); 
	    System.out.println("测试一：硬币数为：" + collect(coin1, p1)); 
	    System.out.println("路径为:"); 
	    printPath(p1); 
	    int[][] coin2 = { 
		    {0,0,1,0,0,1}, 
		    {0,1,0,1,0,0}, 
		    {1,0,0,0,1,1}, 
		    {0,0,1,0,0,1}, 
		    {1,0,0,0,1,0}, 
		    {1,0,0,0,1,1}
	    };
	    LinkedList<String> p2 = new LinkedList<String>(); 
	    System.out.println("测试二：硬币数为：" + collect(coin2, p2)); 
	    System.out.println("路径为:"); 
	    printPath(p2); 
	    int[][] coin3 = { 
		    {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,1} 
        }; 
 
	    LinkedList<String> p3 = new LinkedList<String>(); 
        System.out.println("测试三：硬币数为：" + collect(coin3, p3)); 
        System.out.println("路径为:"); 
	    printPath(p3); 
	} 
    // 收集银币
	public static int collect(int coin[][], LinkedList<String> P) 
	{ 
		int rowcount = coin.length + 1; 
		int colcount = coin[0].length + 1; 
		int[][] Array = new int[rowcount][colcount]; 
		for (int i = 0; i < rowcount; i++) { 
		    Arrays.fill(Array[i], 0); 
		} 
		for (int i = 1; i < rowcount; i++) { 
		    for(int j = 1; j < colcount; j++) { 
			    Array[i][j] = Math.max(Array[i-1][j], Array[i][j-1]) + coin[i-1][j-1];
            } 
		} 
		int i = rowcount - 1; 
		int j = colcount - 1; 
		while(i > 0 && j > 0) { 
		    P.addFirst("(" + i + "," + j + ")"); 
		    if (Array[i-1][j] > Array[i][j-1]) { 
		    	 i = i - 1; 
		    } 
		    else { 
		    	 j = j - 1; 
		    } 
		}
		P.addFirst("(" + 1 + "," + 1 + ")"); 
		return Array[rowcount-1][colcount - 1]; 
	}
    // 输出路径
	public static void printPath(LinkedList<String> P) 
	{ 
	    for(int i=0;i<P.size();i++) 
	    { 
	    	System.out.println(P.get(i)); 
	    } 
	} 
}