1. 問題

p11200.jpg

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

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

1 ← 入力データの数
15 10 ← それぞれ列数、行数を表す
////\\\////\\// ← 迷路
/\\\\\/\/\/\\/\
\\\//\\\/\////\
//\\\/\///\//\\
\/\//\\/\\\\/\\
////////\\///\/
\\\\\\//\\\\\/\
\\/\//////\\///
\/\\/////\/\/\/
\///\///\\\\//\

3. 計算法

p11200-2.jpg

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

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

Comments are closed.

Post Navigation