1. 問題
上記の通り、各セルには必ず、右下あるいは左下斜めの壁が置かれる。迷路の入口は上、出口は下。左右両側は通行禁止。こういう条件の下で、入口から出口までの異なる通路は果たして何本あるか。ちなみに、右上の迷路では通路が3本、左下の迷路では通路が1本という結果になっている。
2. 入力データの例
上記の左下迷路に対応する入力データは以下の通り。大きくなると、目視での確認は相当きつい。￥は本来はバックスラッシュ\、右下斜めを表しているはずなのに。
1 ← 入力データの数 15 10 ← それぞれ列数、行数を表す ////\\\////\\// ← 迷路 /\\\\\/\/\/\\/\ \\\//\\\/\////\ //\\\/\///\//\\ \/\//\\/\\\\/\\ ////////\\///\/ \\\\\\//\\\\\/\ \\/\//////\\/// \/\\/////\/\/\/ \///\///\\\\//\
3. 計算法
セル(r,c)に位置することは、そのセルの下の端の中央にいることと考える。そうすると、周りの壁の形によって、上記の8通りの進み方がある。
証明はまだしていないが、入口1箇所に対応する出口は高々1箇所。従って、１つの入口に入って探索していき、出口ひとつに出くわしたら、それ以降の探索は打ち切り、つぎの入口から探索し続ける、という戦略を取って問題なさそう。また、異なる入口から入り、最終的に同じ出口にいく通路もないと推測する。