SRM 593 DIV1 Easy - HexagonalBoard (復習××)

February 22, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12784&rd=15705

５角形のセルからなるボードがあり、任意の場所に石が置いてある。
石が隣り合うときは、かならず違う色にしなければいけない。

このとき、全ての石を塗るのに必要な最小の色の数を求める。

解き方

シミュレーションしてみると、色の数は最大３色になることがわかる。
色が０色のときは石がないとき、１色のときは全て独立したセルであることから簡単に判定できるので、２色と３色のときの判定ができればよい。

今回は２色でぬろうとしたときに塗れないとき、つまり隣り合うセルが同じ色になってしまうときに３色を返すようにＤＦＳでコーディングする。

コード

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()

int w,h;
vector<string> B;

int dr[]={-1,-1,0,0,1,1};
int dc[]={0,1,-1,1,-1,0};

class HexagonalBoard {

public:

int dfs(int r,int c,int v){
if(B[r][c]!='X')return 0;
int ret=1;
B[r][c]=(char)(v+'0');
FORE(i,0,6){
int nr=r+dr[i],nc=c+dc[i];
if(0<=nr&&nr<h&&0<=nc&&nc<w&&B[nr][nc]!='-'){
if(B[nr][nc]==(char)(v+'0'))ret=3;
else{
ret=max(ret,2);
ret=max(ret,dfs(nr,nc,!v));
}
}
}
return ret;
}

int minColors(vector<string> board) {
B=board;
w=board[0].size(),h=board.size();
int ret=0;
FORE(i,0,board.size())FORE(j,0,board[0].size())ret=max(ret,dfs(i,j,0));
return ret;
}

};

彩色数