SRM 496 DIV1 Easy - ColoredStrokes

SRM 496 DIV1 Easy - ColoredStrokes

16:11

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11306&rd=14425

青を縦に塗ることができるブラシと、赤を横に塗ることができるブラシが
与えられる。

また青と赤が交わったセルは緑色になる。

最初は真っ白なボードからブラシを塗って、最終的に与えられた
形に絵を塗りたいとき、最小の塗る回数を求める。

解き方


緑の色は赤を最初に塗っても、青を最初に塗ってもよく順番は関係ないので、
青の塗る回数と赤を塗る回数を独立で考え、最後に和をとればよい。

コード


class ColoredStrokes {

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

int ret=0;
for(int j=0;j<w;j++){
int at=0;
while(at<h){
while(at<h && (picture[at][j]=='.'||picture[at][j]=='R'))at++;
if(at>=h)break;
ret++;
while(at<h && (picture[at][j]=='G'||picture[at][j]=='B'))at++;
}
}

for(int i=0;i<h;i++){
int at=0;
while(at<w){
while(at<w && (picture[i][at]=='.'||picture[i][at]=='B'))at++;
if(at>=w)break;
ret++;
while(at<w && (picture[i][at]=='G'||picture[i][at]=='R'))at++;
}
}

return ret;
}

};

Share this

Google Facebook Twitter More

Related Posts