課題９４：一方通行の街を通り抜ける
街 $C$ は $n$ 個の交差点から成っています。この街は一方通行の道が多く、どの交差点からどの交差点に行けるかは正方行列 $G$ で表されています。交差点 $i$ から交差点 $j$ に行ける場合は $G_{i,j} = 1$, 行けない場合は $G_{i,j} = 0$ です（ただし $0$ ≤ $i, j$ ≤ $n - 1$）。双方向通行が可能な場合は $G_{i,j} = G_{j,i} = 1$ となっています。いま、街 $C$ に交差点 $0$ から入り、交差点 $n - 1$ から出て通り抜けようとしています。通り抜けることができる経路を全て列挙する関数を作成してください。ただし、同じ交差点は２度通らないこととします。また、通り抜けることができない場合は、空の配列を返すようにしてください。
例1
n = 5
G = \
[[0, 0, 1, 0, 0],
[1, 0, 1, 0, 0],
[0, 0, 0, 1, 0],
[1, 0, 1, 0, 1],
[0, 0, 1, 0, 0]]
[[0, 2, 3, 4]]
例2
n = 8
G = \
[[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0]]
[[0, 1, 4, 7], [0, 1, 3, 6, 7]]
例3
n = 8
G = \
[[0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 0, 0]]
[[0, 7],
[0, 5, 2, 6, 3, 7],
[0, 5, 2, 3, 7],
[0, 5, 1, 6, 3, 7],
[0, 5, 1, 6, 2, 3, 7]]
例4
n = 8
G = \
[[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 1, 0]]
[]
課題提出方法
-
基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。
-
課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。
-
ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。
-
質問・感想・要望などございましたらぜひ書き込んでください。
-
もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。
-
課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。