パズル万華鏡

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

最短コース問題(4)

 最短コース問題(4)を紹介します。

 

問題(4)

 道路が碁盤の目になっているn×nの町がある。点線のところは通れないとして、左上隅の交差点aから右下隅の交差点bまでの最短コースの数は何通りあるか考察せよ。
ただし、道路は、縦にn+1本、横にn+1本あるとし、交差点間の距離は同じとする。

また、交差点を(i,j)で表す。すなわち、下方向にi+1本目、右方向にj+1本目の道路が交わる交差点である。

   左上隅の交差点は(0,0)、
   左下隅の交差点は(n,0)、
   右上隅の交差点は(0,n)、
   右下隅の交差点は(n,n)

とする。

左上隅交差点(0,0)から交差点(i,j) (i≦j)までの最短コースの数をf(i,j)とする。

f:id:isemba:20180403184456p:plain

f(i,j)が満たす漸化式を求めよ。

f:id:isemba:20180403184522j:plain