日期:2014-05-20 浏览次数:20744 次
import java.util.*; public class Test { static class DataNode { //定义一个类用于记录数组元素的位置的值 int x, y, value; public DataNode(int x, int y, int value) { this.x = x; this.y = y; this.value = value; } } static class DataList implements Comparable<DataList> { //定义一个类用于记录路径 int sum = 0; List<DataNode> nodes = new ArrayList<DataNode>(); public DataList() {} public void addNode(DataNode node) { nodes.add(0, node); sum += node.value; } public int compareTo(DataList dl) { return dl.sum - sum; } } public static void main(String[] args) throws Throwable { int[][] number={ {22,32,14,77,45}, {0,12,34,37,23}, {0,0,44,23,15}, {0,0,0,34,54}, {0,0,0,0,88}}; List<DataList> result = findAll(number, 0, 0); //获取所有路径 if (result.size() > 0) { Collections.sort(result); //降序排序所有路径 //for (DataList dl : result) { DataList dl = result.get(0); //取出第一条路径(该路径权值最大) System.out.printf("sum=%d\n", dl.sum); for (DataNode n : dl.nodes) { System.out.printf("(%d,%d:%d), ", n.x, n.y, n.value); } System.out.println(); //} } } //定义一个递归寻找所有路径的方法 public static List<DataList> findAll(int[][] number, int x, int y) { if (number==null || number.length==0 || number[0].length==0) { return new ArrayList<DataList>(); //非法数据的时候返回0元素的集合 } List<DataList> result = new ArrayList<DataList>(); if (x==number.length-1 && y==number[0].length-1) { //路径走到终点的时候递归结束 DataList dl = new DataList(); dl.addNode(new DataNode(x, y, number[x][y])); result.add(dl); return result; } if (x < number.length && y < number[0].length) { //右下有效时递归取右下路径集合 List<DataList> tmp = findAll(number, x+1, y+1); for (DataList dl : tmp) { //在递归获取的子集合中追加当前元素 dl.addNode(new DataNode(x, y, number[x][y])); } result.addAll(tmp); //把右下方的子集合路径追加到最终的结果集中 } if (y < number[0].length) { //右方有效时递归取右方路径集合 List<DataList> tmp = findAll(number, x, y+1); for (DataList dl : tmp) { //同上 dl.addNode(new DataNode(x, y, number[x][y])); } result.addAll(tmp); } if (x < number.length) { //下方有效时递归取下方有效集合 List<DataList> tmp = findAll(number, x+1, y); for (DataList dl : tmp) { //同上 dl.addNode(new DataNode(x, y, number[x][y])); } result.addAll(tmp); } return result; } }
------解决方案--------------------
数可以为负数没