UVa #11200 – Sapitaur's labyrinth

1. 問題

上記の通り、各セルには必ず、右下あるいは左下斜めの壁が置かれる。迷路の入口は上、出口は下。左右両側は通行禁止。こういう条件の下で、入口から出口までの異なる通路は果たして何本あるか。ちなみに、右上の迷路では通路が3本、左下の迷路では通路が1本という結果になっている。

2. 入力データの例
　上記の左下迷路に対応する入力データは以下の通り。大きくなると、目視での確認は相当きつい。￥は本来はバックスラッシュ\、右下斜めを表しているはずなのに。

3. 計算法

セル(r,c)に位置することは、そのセルの下の端の中央にいることと考える。そうすると、周りの壁の形によって、上記の8通りの進み方がある。

証明はまだしていないが、入口1箇所に対応する出口は高々1箇所。従って、１つの入口に入って探索していき、出口ひとつに出くわしたら、それ以降の探索は打ち切り、つぎの入口から探索し続ける、という戦略を取って問題なさそう。また、異なる入口から入り、最終的に同じ出口にいく通路もないと推測する。