問題
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;
}
};
Share this
Related Posts
SRM 391 DIV1 Easy - IsomorphicWords
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8175&rd=11125
解き方
全ての文字について、可能な限り昇順になるように- SRM 538 DIV1 Easy - EvenRoute
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11808&rd=14729
解き方
（ｘ，ｙ）の合計が奇数の座標と偶数の座標が存
- SRM 504 DIV1 Easy - MathContest
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11233&rd=14433
解き方
キューが連続的になっているということに気をつ
- SRM 499 DIV1 Easy - ColorfulRabbits
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11327&rd=14428
様々な種類のうさぎがいる。
そのうちいくつかのうさぎに質問し