SRM 517 Div2 250pt: MonochromaticBoard

TopCoder

問題概要

W*H(W,H<50)のボードがあり、最初は真っ白に塗られている。ボードの列か行を選んで全部黒くする、という作業を繰り替えしてボードをある色に塗り替えたい。作業の必要回数を最小化する問題。

考えたこと

  • うん？これ最小点被覆(Asteroids POJ 3041, 蟻本205p)？(与えられた盤面を真っ黒にする問題かと思ってた)
  • でもDiv2 250でそんなの出る訳無いよね。
  • 問題文を読み返してやっと正しく理解した。
  • 真っ黒な列、行の数を数えるだけに見える。
  • ただし全部黒のときは例外か。
  • 書く。無事通った。

practiceで通ったコード

計算量O(W*H)。

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct MonochromaticBoard {

	int theMin(vector <string> board) {
		const int H = board.size(), W = board[0].length();

		//全部黒
		bool is_white = false;
		for(int i=0; i<H; i++){
			for(int j=0; j<W; j++){
				is_white |= board[i][j] == 'W';
			}
		}
		if(!is_white){
			return min(H, W);
		}


		int ret = 0;

		//横に塗る
		for(int i=0; i<H; i++){
			bool is_white = false;
			for(int j=0; j<W; j++){
				is_white |= board[i][j] == 'W';
			}

			if(!is_white){
				ret++;
			}
		}

		//縦に塗る
		for(int j=0; j<W; j++){
			bool is_white = false;
			for(int i=0; i<H; i++){
				is_white |= board[i][j] == 'W';
			}

			if(!is_white){
				ret++;
			}
		}

		return ret;
	}

};