blue_jamのTopCoder日記

SRM494 Div1 Easy

SRM, Practice | 14:23

概要

ピクセルの情報が与えられるので，それを塗りつぶすことができる最大のブラシの大きさを求める．

解法

O(min(W,H) * (WH)^2)で全部ぬって確かめる．

O(WH)でいけない気がしなくもない．

なんかすごい時間かかった．

class Painting {
public:
    int largestBrush(vector <string> picture) {
        int w, h;
        bool checked[60][60];
        w = picture[0].size(); h = picture.size();
        for(int k=1;k<=min(w,h);++k){
            bool filled;
            memset(checked, 0, sizeof(checked));
            for(int i=0;i+k<=h;++i){
                for(int j=0;j+k<=w;++j){
                    bool flag = true;
                    for(int ti=0;ti<k;++ti){
                        for(int tj=0;tj<k;++tj){
                            if(picture[i+ti][j+tj] == 'W'){
                                flag = false;
                            }
                        }
                    }
                    if(flag){
                        for(int ti=0;ti<k;++ti){
                            for(int tj=0;tj<k;++tj){
                                checked[i+ti][j+tj] = true;
                            }
                        }
                    }
                }
            }
            filled = true;
            for(int i=0;i<h;++i){
                for(int j=0;j<w;++j){
                    if(picture[i][j] == 'B' && !checked[i][j]){
                        filled = false;
                    }
                }
            }
            if(!filled) return k - 1;
        }
        return min(h, w);
    }
};