`

创建一个二维数组,求路线,使得和最小

阅读更多
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * 创建一个二维数组,每一个元素是一个正数。<br>
 * 进行走位,路线是从数组左上角走到右下角。<br>
 * 每次只能向右或向下走。<br>
 * 不能走出矩阵。<br>
 * 走一步就会加上当前数组中元素的数据。<br>
 * 求路线,使得和最小。
 * 
 * @author 刘胜军
 */
public class Seven {

	public static void main(String[] args) {
		/********************************************/
		int[][] num = getMiGong();// 获取迷宫
		Stack<Object[]> end = new Stack<Object[]>();// 保存所有通路栈
		Stack<Position> temp = new Stack<Position>();// 保存当前走过的路的坐标的栈
		new Seven().getRu(0, 0, num.length - 1, num[0].length - 1, temp, end);// 计算

		/**************** 打印所有通路 ******************/
		for (Object[] obj : end) {
			System.out.println(Arrays.toString(obj));
		}
		/***************** 获取最小值 ******************/
		int index_i = 0;// 当前最小值的下标
		int index_sum = Integer.MAX_VALUE;// 记录当前最小值
		for (int i = 0; i < end.size(); i++) {
			int size = 0;
			for (Object object : end.get(i)) {
				size += num[((Position) object).row][((Position) object).col];
			}
			if (size <= index_sum) {
				index_i = i;
				index_sum = size;
			}
		}
		System.out.println("最小权值为:" + index_sum);
		System.out.println("最小权值坐标为:" + Arrays.toString(end.get(index_i)));
		/********************************************/
	}

	/**
	 * 获取矩阵
	 * 
	 * @return
	 */
	public static int[][] getMiGong() {
		int x = new Random().nextInt(9) + 1;
		int y = new Random().nextInt(9) + 1;
		int[][] num = new int[x][y];

		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				num[i][j] = new Random().nextInt(100);
			}
		}

		// int[][] num = { { 1, 1, 1, 1, 1 },

		// int[][] num = { { 1, 0, 1, 1, 1 }, { 1, 0, 1, 1, 1 },
		// { 1, 0, 0, 0, 1 }, { 1, 1, 0, 0, 1 }, { 1, 1, 1, 1, 1 } };

		// int[][] num = { { 1, 1, 1, 1, 1, 1, 1, 1, 1 },
		// { 1, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 0, 1, 1, 0, 1 },
		// { 1, 0, 1, 0, 0, 1, 0, 0, 1 }, { 1, 0, 1, 0, 1, 0, 1, 0, 1 },
		// { 1, 0, 0, 0, 0, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1, 0, 1, 1, 1 },
		// { 1, 0, 0, 0, 0, 0, 0, 0, 1 } };
		return num;
	}

	/**
	 * 计算所有通路
	 * 
	 * @param start_x
	 *            开始坐标x
	 * @param start_y
	 *            开始坐标y
	 * @param end_x
	 *            结束坐标x
	 * @param end_y
	 *            结束坐标y
	 * @param temp
	 *            保存当前走过的路的栈
	 * @param end
	 *            保存通路的栈
	 */
	public void getRu(int start_x, int start_y, int end_x, int end_y,
			Stack<Position> temp, Stack<Object[]> end) {
		temp.push(new Position(start_x, start_y));// 当前点入栈
		if (start_x == end_x && start_y == end_y) {// 判断当前点是不是结束点
			end.push(temp.toArray());// 如果是,说明当前是一条通路,这个时候保存当前通路保存到通路的栈中
			temp.pop();// 当前点出栈
			return;// 返回上一个点(最后一个点的话,退出当前方法)
		}
		if (start_x + 1 <= end_x)
			getRu(start_x + 1, start_y, end_x, end_y, temp, end);
		if (start_y + 1 <= end_y)
			getRu(start_x, start_y + 1, end_x, end_y, temp, end);
		temp.pop();// 当前点出栈
		return;// 返回上一个点(最后一个点的话,退出当前方法)
	}

	/**
	 * 自定义点坐标
	 * 
	 * @author 刘胜军
	 */
	class Position {
		public int row;
		public int col;

		public Position(int row, int col) {
			this.row = row;
			this.col = col;
		}

		public int getRow() {
			return row;
		}

		public int getCol() {
			return col;
		}

		@Override
		public String toString() {
			return "(" + row + "," + col + ")";
		}
	}
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics