パズル万華鏡

面白いパズルの紹介と解説をします。

n回曲がる最短経路問題・考察(1)

 n回曲がる最短経路問題・考察(1)を示します。

(考察1)
 n×nの格子状の道路がある町を考える。交差点Aから交差点Bまで、最短経路で移動する。ただし、交差点間の距離は同じとする。

 n=1,2,…,9について、k回曲がる経路数を求めた。
f:id:isemba:20160901112618j:plain
●プログラム(CB111.bas)

' << CB111.bas >>
' n×nの格子状の道路がある町
'
Public COUNT(99): ' COUNT(I):I(1≦I≦2n-1)回曲がる
                  ' 最短経路の個数。
Public N:         ' nの値。                   
Public C(99):     ' 組合せを保存する配列。    
'
Do
  ' Nの読み込み。
  Read N
  If N <= 0 Then EXit Do
  '
  ' 初期設定。
  For I=1 To 2*N-1: COUNT(I)=0: Next I
  '
  ' 組合せの生成。
  Call Comb(1)
  ' 
  ' 結果の表示。
  Print Using"##×##の格子状の道路";N;N
  Print"曲がる回数  経路数"
  For I=1 To 2*N-1
    Print Using"   ####  ######";I;COUNT(I)
  Next I
  Print
Loop
End
'
' 2n個からn個取りだす組合せ生成プログラム。
Sub Comb(K)
  If K > 2*N Then        
    T=0
    For J=1 To 2*N: T=T+C(J): Next J   
    If T = N Then 
      S=0
      For J=2 To 2*N
        If C(J-1) <> C(J) Then S=S+1
      Next J
      COUNT(S)=COUNT(S)+1
    End If                                               
  Else                                           
    C(K)=0: Call Comb(K+1)
    C(K)=1: Call Comb(K+1)                               
  End If                                                  
End Sub
'
' データ。
Data 2, 3, 4, 5, 0

実行結果
2× 2の格子状の道路
曲がる回数  経路数
    1   2
    2   2
    3   2

3× 3の格子状の道路
曲がる回数  経路数
    1   2
    2   4
    3   8
    4   4
    5   2

4× 4の格子状の道路
曲がる回数  経路数
    1   2
    2   6
    3   18
    4   18
    5   18
    6   6
    7   2

5× 5の格子状の道路
曲がる回数  経路数
    1   2
    2   8
    3   32
    4   48
    5   72
    6   48
    7   32
    8   8
    9   2

OK
f:id:isemba:20160901112938j:plain