Mujin Programming Challenge 2017 B - Row to Column
問題概要
黒色と白色のマス目で構成されたマス目が与えられる。操作(問題文参照してください)を行って全てのマスを黒色にする場合の最小の操作回数を求める。
解法
まず、黒色のマスが初期状態で存在しない場合、無から有は錬成できないので、答えは-1となる。
次に、いずれかの行に含まれるマス目を全て黒色にすることを考える。すると、各列について、もしその列に黒いマスが含まれるのならば、その列を全て黒色にするためにはその列に含まれる白色のマスの個数、含まれないならその列に含まれる白色のマスの個数+1回の操作が必要となる。
1つの行を全て黒色にすることができれば、他の条件を満たしていない(白色のマスが含まれている)列の個数分適切に操作を行うことにより、全てのマスを黒色にすることができる。
よって、-1にならない場合、1つの行を全て黒にする最小値+白色のマスが含まれる列が答えとなるのでこれを実装して、AC。
