最短経路の場合の数の問題を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)