package com.softeem.exam2;

import java.util.ArrayList;
import java.util.List;

public class Test8 {

	public static void main(String[] args) {

		//定义一个二维数组
		int[][] nums = new int[5][6];
		//通过循环随机向二维数组中添加数据
		for (int i = 0; i < nums.length; i++) {
			for (int j = 0; j < nums[i].length; j++) {
				nums[i][j] = (int)(Math.random()*9+1);
			}
		}
		//显示二维数组中元素
		for (int i = 0; i < nums.length; i++) {
			for (int j = 0; j < nums[i].length; j++) {
				System.out.print(nums[i][j]+"\t");
			}
			System.out.println();
		}

		//声明数组保存数组中相邻三个元素
		int[] nos = new int[3];
		//声明一个集合保存找到的最小数字
		List<Integer> lists = new ArrayList<Integer>();
		//将开始位置数字放入集合中
		lists.add(nums[0][0]);
		//声明变量保存所在位置
		int m = 0, n = 0;
		//通过循环找出路径
		while(m <= 4 && n <= 5){
			
			//当没走到最边上的时候
			if(m < 4 && n < 5){	
				//将数组中相邻三个元素保存到数组中
				nos[0] = nums[m][n+1];
				nos[1] = nums[m+1][n];
				nos[2] = nums[m+1][n+1];
				//遍历数组找出最小的数及下标
				int min = nos[0];
				int index = 0;
				for (int k = 0; k < nos.length; k++) {
					if(min >= nos[k]){
						min = nos[k];
						index = k;
					}
				}	
				
				//判断最小路线并将数字保存到集合中,重新定位所在位置
				if(index == 0){
					lists.add(nos[0]);
					n += 1;
				}else if(index == 1){
					lists.add(nos[1]);
					m += 1;
				}else{
					lists.add(nos[2]);
					m += 1;
					n += 1;				
				}				
			}else if(m < 4 && n == 5){		//当走到最右边列上的时候
				lists.add(nums[m+1][n]);
				m += 1;
			}else if (m == 4 && n < 5){		//当走到最下边行上的时候
				lists.add(nums[m][n+1]);
				n += 1;
			}else{							//当走到右下角的时候，退出循环
				break;
			}
		}	
		
		//遍历集合输出最终经过路线
		System.out.print("\n最小和是：");
		for (int j = 0; j < lists.size(); j++) {
			
			if(j == lists.size()-1){				
				System.out.print(lists.get(j));
				break;
			}			
			System.out.print(lists.get(j)+"+");
		}		
	}
}