SRM 631 DIV1 Easy - TaroJiroGrid (復習×)

September 19, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13393&rd=16062

N*Nのボードがあり、WかBの色が塗られている。
１回の操作で１つの行の色をWかB一色にすることができる。

このとき、全ての列について、同じ色がN/2より多く連続しないようにするための
最小の操作回数を求める。

解き方

同じ色がN/2より多く連続しない、というのがポイント。
最悪のケースでは、N/2行とN/2+1行を別の色にすれば条件を満たすのでよいので２回で済む。

よって、操作回数０回と１回の場合を全探索すればよい。

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class TaroJiroGrid {

public:

bool check(vector<string> g){
int n=g.size();

FORE(j,0,n){
char prev=g[0][j];
int cnt=1;
FORE(i,1,n){
if(g[i][j]==prev)cnt++;
else{
if(cnt>n/2)return false;
prev=g[i][j];
cnt=1;
}
}
if(cnt>n/2)return false;
}
return true;
}

int getNumber(vector<string> grid) {
if(check(grid))return 0;

int n=grid.size();

FORE(i,0,n){
vector<string> tmp=grid;
FORE(j,0,n)tmp[i][j]='W';
if(check(tmp))return 1;

tmp=grid;
FORE(j,0,n)tmp[i][j]='B';
if(check(tmp))return 1;
}

return 2;
}

};

考察