A63
|
交差点と交差点の間の短い道を1本の道と考えましょう。 基本的に、右と上に進む限り（左と下に戻らない限り）、 どんな道を選んでも右に5本、上に5本進むことになるので、 最短ルートは何通りもあるように思えます。 しかし、必ずしも道の中心を歩かなければならないわけでは ないので、この図 のようにコーナーを絶妙に突いていけば(^ ^) さらに短い距離でゴールに辿り着くことができますね。 壁が無い場合の最短距離は、もちろんスタートとゴールを結ぶ 直線なので、それにできるだけ近いルートを進むように するわけです。 よって答えはこの場合と、最初に上に進む場合の2通りが 考えられます。 |