Description:
n*mのマスがある。(2 <= n,m <= 9)
各マスは、空き、障害物、マーク2、マーク3のうちのどれかとなっている。
マーク2,3はそれぞれ2つずつ存在する。
同じマーク同士をワイヤーで結びたい。
障害物のあるマスや、既にワイヤーが通っているマスにワイヤーを通すことは出来ない。
必要なワイヤーの長さを求めよ。
不可能なら、0と表示せよ。
Answer:
2のワイヤーの引き方を枝刈り付きDFSで全部作り、そのフィールドで3のワイヤーを幅優先で引く。
枝狩りは、
1. あと一歩で2のゴールに着くなら、そこへ向かって引く。
2. 二つ以上前に引いた自分の線の隣に来たら、無駄なループが出来ているので枝狩り。
3. 右(左)に曲がる、直進、右(左)に曲がると引いた時に、囲んだ場所に何も無ければ余計な遠回りをしているので枝狩り。
4. 右(左)に曲がる、直進、直進、右(左)に曲がるで、同様の場合に枝狩り。
を行えば、9*9の場合はなんとかする事が出来る。
9 9
2 0 0 0 0 0 0 3 2
0 0 0 0 0 0 0 0 3
0 0 0 .....
というフィールドで、左上からDFSを行うと、関数がDFS関数が350万回ほど呼ばれる事になる。
しかし、同様な10*10のフィールドでは、9千万回、11*11では35億回となり、解けない。
計算量の見積もりが立てにくい為、コンテスト本番では手を出しにくい問題だ。
Source: