読者です 読者をやめる 読者になる 読者になる

hogloidのブログ

へなちょこ

PKU 1548 Robots

http://poj.org/problem?id=1548
解いてるとき日本語で解説されたソースコードがなくて困ったので書きます

まず、最初は0,0の場所にいます。
もし0行目にゴミがあるなら、一番右にあるゴミまで取ります(そこまで行かなければまたそのゴミを取りにいかなければならないから)
0行目のゴミを取ったら一つ下の行へ移動します。この時新しい行の右にゴミがある時、そのすべてのゴミを取りにいきます。(ここでそのゴミを取っておけば次にその行を掃除するときさらに右へ行く必要がありません。つまり次行くときは今より左な状態で次の行へ行けます。)

そんな感じでどんどん潜って行きます。説明下手ですいません

int main(){
	vvi buf(25,vi(25));
	int a,b;
	while(cin>>a>>b && (a!=-1&& b!=-1)){
		REP(i,25) fill(ALL(buf[i]),0);
		int dust=0;
		while((a||b)){
			--a;--b;
			buf[a][b]=1;
			++dust;
			cin>>a>>b;
		}
		if(!dust){
			cout<<0<<endl;
			continue;
		}
		int res=0;
		int right=0,left=0,flag;
		while(1){
			flag=0;
			right=left=0;
		REP(y,25){
			REPN(i,25,left){
				if(buf[y][i]){
					flag=1;
					right=i;
					buf[y][i]=0;
				}
			}
			left=right;
		}
		if(flag) ++res;
		if(left==0) break;
		}
		cout<<res<<endl;
	}
	return 0;
}