SRM 494 DIV1 Easy - Painting ○

SRM 494 DIV1 Easy - Painting ○

16:06

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11310&rd=14423

白いボードが与えられる。
これをN＊Nの黒いスタンプによって、与えられた絵を作りたい。
できるだけ大きいスタンプで与えられた絵を作りたいとき、
その最大の大きさを求める。

解き方


スタンプを押す順番は関係ないので、各スタンプの大きさについて
スタンプが押せる位置のとき、スタンプを押してしまう。
押したスタンプのセルを？とし、最後にWと？だけが残れば
その大きさのスタンプで絵を作ることができる。

コード


class Painting {

public: int largestBrush(vector<string> picture) {
int h=picture.size(),w=picture[0].size();

for(int len=min(w,h);len>=2;len--){
vector<string> p=picture;
while(1){
int finish=1;
for(int i=0;i+len-1<h;i++)for(int j=0;j+len-1<w;j++){
int valid=1;
for(int k=i;k<i+len;k++)for(int l=j;l<j+len;l++){
if(p[k][l]=='W')valid=0;
}
if(valid){
for(int k=i;k<i+len;k++)for(int l=j;l<j+len;l++){
if(p[k][l]=='B')finish=0;
p[k][l]='?';
}
}
}
if(finish)break;
}
int flag=1;
FORE(i,0,h)FORE(j,0,w)if(p[i][j]=='B')flag=0;
if(flag)return len;
}

return 1;
}

};

Share this

Google Facebook Twitter More

Related Posts