最短経路の場合の数の問題をJavaで解いてみた。

 最短経路の場合の数の問題Javaで解いてみました。(^_^;
 [S/G]型(左下スタート、右上ゴール)の問題が多いので、まず、[S/G]型のマップを文字列で与えて、計算しやすいように、[S\G]型(左上スタート、右下ゴール)の数値マップに変換しています。ただし、辺は1、他は0で与えました。
 ちなみに、[S/G]型、[S\G]型とは、模式図的に書くと次の通りです。

    G                                S
[ / ]型(左下スタート、右上ゴール)、[ \ ]型(左上スタート、右下ゴール)
 S                                      G

 また、iMapの点の位置には、Sだけ1、他の点は0を和の初期値として与えて、左または上に辺があれば前の点の和を足して和を求めていきます。
 最後に、出力は、[S/G]型に戻しています。
 ちなみに、sMapのところを適当に変えると、カタラン数などの他の問題も解くことができます。

●NumOfShortestPath01.java

/* 
 * NumOfShortestPath01.java
 * 
 * 最短経路の場合の数
 * 
 *  [S/G]            [S\G]
 * "     +-+-+-G"    "            "    [000000000000]
 * "     | | | |"    " S-+-+-+    "    [001010100000]
 * " +-+-+-+-+-+"    " | | | |    "    [010101010000]
 * " | | | | | |"    " +-+-+-+    "    [001010100000]
 * " +-+-+-+-+-+" -> " | | | |    " -> [010101010000]
 * " | | | |    "    " +-+-+-+-+-+"    [001010101010]
 * " +-+-+-+    "    " | | | | | |"    [010101010101]
 * " | | | |    "    " +-+-+-+-+-+"    [001010101010]
 * " S-+-+-+    "    "     | | | |"    [000001010101]
 * "            "    "     +-+-+-G"    [000000101010]
 * 
 * ※辺は1、他は0
 * 
 */

public class NumOfShortestPath01 {
    public static void main(String[] args) {
        long tm=System.nanoTime();  // Timer Start
        String sMap[]={
            "     +-+-+-G",
            "     | | | |",
            " +-+-+-+-+-+",
            " | | | | | |",
            " +-+-+-+-+-+",
            " | | | |    ",
            " +-+-+-+    ",
            " | | | |    ",
            " S-+-+-+    ",
            "            ",
        };
        int m=sMap.length;
        int n=sMap[0].length();
        
        int[][] iMap = new int[m][n];
        for(int i=0, k=m-1; i< m; i++, k--) {
            for(int j=0; j< n; j++) {
                switch(sMap[i].charAt(j)) {
                    case '|':
                    case '-':
                        iMap[k][j]=1;
                        break;
                    default:
                        iMap[k][j]=0;
                }
            }
        }
        
        iMap[1][1]=1;               // 和の初期値。Sだけ1、他の点は0
        for(int i=1; i< m; i+=2) {
            for(int j=1; j< n; j+=2) {
                if(iMap[i][j-1]==1) iMap[i][j]+=iMap[i][j-2];
                if(iMap[i-1][j]==1) iMap[i][j]+=iMap[i-2][j];
            }
        }
        
        for(int i=m-1; i>=1; i-=2) {
            for(int j=1; j< n; j+=2)
                System.out.printf("%4d",iMap[i][j]);
            System.out.println();
        }
        System.out.println();
        tm=System.nanoTime()-tm;    // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

   0   0  10  30  60 100
   1   4  10  20  30  40
   1   3   6  10  10  10
   1   2   3   4   0   0
   1   1   1   1   0   0

Runtime : 0.035 [sec]

※参考URL
立体の最短経路の場合の数の問題をJavaで解いてみた。
立体の最短経路の場合の数の問題をJavaで解いてみた。(2)