PKU 2734 Queens, Knights and Pawns

http://poj.org/problem?id=2734
大きさn*mのチェス盤の上で、ナイト、クイーン、ポーンのコマの配置がわかっている。
このとき、どのコマの攻撃範囲にも入っていないマスの個数を求めろというような問題。
ポーンは場所だけを占有し、クイーンは他のコマによって移動を邪魔されるものとする。

簡単なシミュレーション？。
クイーンを一番最後に処理するのが多少かったるい。

int n,m;
int boa[1000][1000];

int solve(){
  memset(boa,0,sizeof(boa));
  vector<PI> q;
  int k;
  cin>>k;
  rep(i,k){
    int x,y;
    cin>>x>>y;
    q.pb(mp(x-1,y-1));
  }
  cin>>k;
  int tx[]={1,2,2,1,-1,-2,-2,-1};
  int ty[]={2,1,-1,-2,-2,-1,1,2};
  
  rep(i,k){
    int x,y;
    cin>>x>>y;
    --x,--y;
    boa[x][y]|=1;
    rep(j,8){
      int nx=x+tx[j],ny=y+ty[j];
      if(0>min(nx,ny) ||
         nx>=n || ny>=m)continue;
      boa[nx][ny]|=2;
    }
  }
  cin>>k;
  rep(i,k){
    int x,y;
    cin>>x>>y;
    boa[x-1][y-1]|=1;
  }

  FOR(it,q){
    int x=it->F,y=it->S;
    boa[x][y]|=1;
    rep(i,8){
      int nx=x,ny=y;
      while(true){
        nx+=dx[i];
        ny+=dy[i];
        if(0>min(nx,ny) ||
           nx>=n || ny>=m ||
           (boa[nx][ny]&1))break;
        boa[nx][ny]|=2;
      }
    }
  }
  int ans=0;
  rep(i,n)rep(j,m)
    ans+=!boa[i][j];
  return ans;
}

main(){
  int bo=0;
  while(cin>>n>>m,n|m)
    printf("Board %d has %d safe squares.\n",++bo,solve());
}