首页 > 代码库 > 矩阵中的最小路径

矩阵中的最小路径

package 数阵中的最优路径;import java.util.Scanner;public class Main2 {        /**     * 数阵中的最小路径搜索     * 1:设计要点     * 应用动态规划设计从右下角逐行至左上角,确定n,m后,随机产生的整数二维数组a(n,m)作矩阵输出同时赋值给部分和数组b(n,m).     * 数组b(i,j)为点(i,j)到到右下角的最小数值和stm(i,j)是点(i,j)向右(R)或向下(D)或向右下(0)的路标数组     * 注意到最后一行与最后一列各数只有一个出口,于是b[n][m]开始向左逐个推出同行的b[n][j](j=m-1,.....1);想上逐个推出同列     * b(i,m)(i = n-1,......1);     * b(i,j)与stm(i,j)的值,由同一列下面的值b(i+1,j),与同一行右边的值b(i,j+1),其右下方的值b(i+1,j+1)值决定。     * 设min = min(b(i+1,j+1),b(i+1,j),b(i,j+1))     * 首先作赋值min=b(i+1,j+1),stm(i,j) = "0"     * 如果b(i,j+1)<min,则min=b(i,j+1);stm(i,j) = "R"     * 如果b(i+1,j)<min,则min=b(i+1,j);stm(i,j) = "D"     * 然后赋值b(i,j) = b(i,j)+min.     *      *      *      *      *      * @param args     */    public static void main(String[] args) {        Scanner input = new Scanner(System.in);        System.out.println("输入行数:");        int n = input.nextInt();        System.out.println("输入列数:");        int m = input.nextInt();                int a[][] = new int[30][30];        int b[][] = new int[30][30];        char[][]stm = new char[30][30];                                        //输出矩阵        for(int i=1;i<=n;i++)        {            for(int j = 1;j<=m;j++)            {                a[i][j] = (int)(Math.random()*20+1);                b[i][j] = a[i][j];                System.out.printf("%4d",a[i][j]);            }            System.out.println();        }                //计算最小路径        for(int j = m-1;j>=1;j--)//第n行递推为边界条件        {            b[n][j]+=b[n][j+1];            stm[n][j]=‘R‘;        }                for(int i = n-1;i>=1;i--)//第m列递推为边界条件        {            b[i][m]+=b[i+1][m];            stm[i][m]=‘D‘;        }                //逆推求取最小值        for(int i=n-1;i>=1;i--)            for(int j = m-1;j>=1;j--)            {                int min = b[i+1][j+1];                stm[i][j] = ‘0‘;                if(min > b[i+1][j])                {                    min = b[i+1][j];                    stm[i][j]=‘D‘;                }                                if(min > b[i][j+1])                {                    min = b[i][j+1];                    stm[i][j] = ‘R‘;                }                b[i][j]+=min;            }                System.out.println(b[1][1]);                                    }}

 

 

 

矩阵中的最小路径