OMC225(D)

点数: 400

Writer: natsuneko

　正方形 $ABCD$ があり，各辺を $4$ 等分するような点によって $16~(=4\times 4)$ 個の小正方形に分かれるように線を引きます．さらに，以下の操作を $3$ 回行います．ここで，各時点で「小正方形」といったとき，その内部（周上を除く）にいかなる線も引かれていないものをさすものとします．

• 線分 $AC$ が内部（周上を除く）を通るような小正方形それぞれが，各辺の中点によって$4~(=2\times 2)$ 個の小正方形に分かれるように線を引く．

最終的な状況において，線の上のみを通って$A$ から $C$ まで最短で到達する方法の総数を求めてください．

$1$ 回目の操作が終了した時点の図

$2$ 回目の操作が終了した時点の図

すべての操作が終了した時点の図