問題
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;
}
};
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;
}
};