PKU 1548 Robots

http://poj.org/problem?id=1548
下と右にしか移動できないロボットを使って、二次元フィールド上のゴミを集めるために必要なロボットの最小個数を求めろというような問題。

ロボットに貪欲に自分と同じ列のゴミを拾い集めさせるシミュレーションをして数えました。

bool lit[50][50];

main(){
  int r,c;
  while(cin>>r>>c,~r){
    memset(lit,0,sizeof(lit));
    lit[r-1][c-1]=true;
    int x,y;
    int num=1;
    while(cin>>x>>y,x){
      lit[x-1][y-1]=true;
      r=max(r,x);
      c=max(c,y);
      ++num;
    }

    int ans=0;
    while(num){
      int cx=0,cy=0;
      ++ans;
      while(cy<c){
        for(int i=cx;i<r;++i){
          if(lit[i][cy]){
            lit[i][cy]=0;
            cx=i;
            --num;
          }
        }
        ++cy;
      }
    }
    cout<<ans<<endl;
  }
}