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

　立体の最短経路の場合の数の問題をJavaで解いてみました。
　ただし、左下スタート、右上ゴール型の問題に直して解きました。(^_^;
　ちなみに、「立体道順」とも呼ばれているようです。sMap={…};のとこだけ書き直せば他の問題も解くことができます。

●NumOfShortestPath3D01.java

/* 
 * NumOfShortestPath3D01.java
 * 
 * 最短経路の場合の数：立体
 * 
 */

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

●実行結果

   6  18  54
   3   6  18
   1   3   6

   3   6  18
   2   0   6
   1   2   3

   1   3   6
   1   2   3
   1   1   1

Runtime : 0.030 [sec]

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

離散数学「数え上げ理論」―「おみやげの配り方」から「Nクイーン問題」まで (ブルーバックス)

上・中級公務員 標準判断推理―確かな解答力が身につく“基本書”