知恵袋で見つけた立体の最短経路の場合の数の問題をJavaで解いてみました。
空間において座標(x,y,z)にある点Pを1回の操作で
(x+1,y,z),(x,y+1,z),(x,y,z+1)
のいずれかを選んでその座標に移動させる。
最初に(0,0,0)にある点Pを、9回の操作で(3,3,3)に移動させる選び方のうち、
(3,0,0),(0,3,0),(0,0,3),(3,3,0),(3,0,3),(0,3,3)
のいずれも経由しないものは何通りあるか求めよ。
この前、作ったのを雛形にしましたが、sMapが煩わしいので略記できるように直しました。(^_^;
● NumOfShortestPath3D02.java
/* * NumOfShortestPath3D02.java * 最短経路の場合の数:立体 * */ public class NumOfShortestPath3D02 { public static void main(String[] args) { long tm=System.nanoTime(); // Timer Start String sMap[][]={ {" +-+-G", // 4 " | | |", " +-+-+-+", " | | | |", " +-+-+-+", " | | ", " +-+ ", " "}, {" +-+-+-+", // 3 " | | | |", " +-+-+-+", " | | | |", " +-+-+-+", " | | | |", " +-+-+-+", " "}, {" +-+-+-+", // 2 " | | | |", " +-+-+-+", " | | | |", " +-+-+-+", " | | | |", " +-+-+-+", " "}, {" +-+ ", // 1 " | | ", " +-+-+-+", " | | | |", " +-+-+-+", " | | | ", " S-+-+ ", " "}, }; int l=sMap.length*2; 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/2; h++, p-=2) { 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 '-': iMap[p][k][j]=1; break; default: iMap[p][k][j]=0; } } } } for(int h=0, p=l-2; h< l/2-1 ; h++, p-=2) { for(int i=0, k=m-1; i< m; i++, k--) { for(int j=0; j< n; j++) { String s = "" + sMap[h][i].charAt(j) + sMap[h+1][i].charAt(j); if(s.equals("++") || s.equals("+S") || s.equals("G+")) iMap[p][k][j]=1; else 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("%5d",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); } }
●実行結果
0 114 522 1566 9 57 204 522 3 18 57 114 0 3 9 0 9 57 204 522 6 30 90 204 3 12 30 57 1 3 6 9 3 18 57 114 3 12 30 57 2 6 12 18 1 2 3 3 0 3 9 0 1 3 6 9 1 2 3 3 1 1 1 0 Runtime : 0.027 [sec]
※参考URL
●最短経路の場合の数の問題をJavaで解いてみた。
●立体の最短経路の場合の数の問題をJavaで解いてみた。