SRM 655 div1 easy BichromePainting
左端から順に塗りつぶして考えていくと、テストケースにうまくいかないものがあり、そこから手が出なかった。
最終状態からk*kの正方形領域内に'B'と'W'の一方のみが存在するものがあれば、その領域を'?'で塗りつぶす。以下これを繰り返して最終的にn*n全体が'?'で埋まればPossible。
Topcoderの問題演習量が圧倒的に足りない感じ。
[参照記事]
SRM 655 div1 easy:BichromePainting - mayoko’s diary
class BichromePainting { public: bool degenerate(vector<string> &b,int y,int x,int k){ int n=b.size(); if(y+k-1>=n || x+k-1>=n) return false; char c='?'; for(int i=y;i<=y+k-1;i++)for(int j=x;j<=x+k-1;j++){ if(b[i][j]!='?'){ if(c=='?'){ c=b[i][j]; }else if(c!=b[i][j]){ return false; } } } if(c=='?') return false; for(int i=y;i<=y+k-1;i++)for(int j=x;j<=x+k-1;j++){ b[i][j]='?'; } return true; } bool isPossible(vector<string> &b){ int n=b.size(); REP(y,n)REP(x,n){ if(b[y][x]!='?') return false; } return true; } string isThatPossible(vector <string> board, int k) { int n=board.size(); bool flag=false;; while(1){ REP(y,n)REP(x,n){ if(degenerate(board,y,x,k)) flag=true; } if(!flag) break; flag=false; } if(isPossible(board)) return "Possible"; else return "Impossible"; } }