TopCoder Open 2R 1000 - BreakingChocolate
問題
W×H に正方形が並べられている中に，特別なマスがいくつか指定されている．垂直／水平に境界線を引いて特殊マスだけが含まれる長方形と特殊マスが含まれない長方形に分割したい．新しい境界線を引く時は既に引かれている境界線を超えてはいけない．十字にしたい時は元の境界線の両側でそれぞれ線を引こう．境界線を引く回数は最小でいくつか？
W×H に正方形が並べられている中に，特別なマスがいくつか指定されている．垂直／水平に境界線を引いて特殊マスだけが含まれる長方形と特殊マスが含まれない長方形に分割したい．新しい境界線を引く時は既に引かれている境界線を超えてはいけない．十字にしたい時は元の境界線の両側でそれぞれ線を引こう．境界線を引く回数は最小でいくつか？