|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
うーむ，最初問題を読み違えて題意を勘違いしており散々でしたが，題意を理解した後も，こんなんでいいのかなぁ，とか思ったり。 「どの１本でも復旧すれば、Ｓ町からＧ町に行くことができるようになる」の「どの１本でも」がポイントでしょうか。 まぁ，一応，こんな感じ。 (解法1) エ，オの状況で分類します。通行可能を○，通行不可能を×，とします。 エが○，オが○の場合：アは×，イは×，ウは○，しかないので，1 通り。 エが○，オが×の場合：アは×，イは○，ウは×，しかないので，1 通り。 エが×，オが○の場合：アは○，イは×，ウは○，しかないので，1 通り。 エが×，オが×の場合：アは○，イは○，ウは○，しかないので，1 通り。 以上ですべてなので，4 通り，になります。 (解法1)で考えているうちに思ったのですが，結局は，次のようにしてもよさそう？ でも，却って面倒ですね。 (解法2) S，A，B，G を S と G が別々になる二つのグループに分け， S のあるグループ内では必ず S から到達でき，G のあるグループ内では必ず G に到達でき， 前者のグループから後者のグループに行けるようにすれば， グループ間の通行を不可能にしたときに題意を満たすので，そのグループの分け方が答えになります(と思います (^^;)。 これは，S と ABG，SA と BG，SB と AG，SAB と G，なので，結局，4 通り，になります。 |
|
ネコの住む家
11月8日（木） 12:44:36
39986 |