PKU 2446 Chessboard

http://poj.org/problem?id=2446
穴の開いたボード上の穴以外の部分に重なりなく1x2の板を敷き詰めることが出来るかを答えろというような問題。

隣あった穴の開いていないマスにエッジを張り、グラフが完全マッチングを作れるかを調べる。

bool ho[320][320];

vector<int> G[3000];
int match[3000];
bool vis[3000];
int m,n,k;

bool augment(int v){
  vis[v]=true;
  rep(i,SZ(G[v])){
    int to=G[v][i];
    if(match[to]==-1){
      match[to]=v;
      match[v]=to;
      return true;
    }
    if(vis[match[to]])continue;    
    if(augment(match[to])){
      match[to]=v;
      match[v]=to;
      return true;
    }
  }
  return false;
}

main(){
  memset(match,-1,sizeof(match));
  cin>>m>>n>>k;
  rep(i,k){
    int x,y;
    cin>>x>>y;
    ho[y-1][x-1]=true;
  }
  rep(i,m){
    rep(j,n){
      if(ho[i][j])continue;
      rep(k,4){
        int ni=i+dx[k],nj=j+dy[k];
        if(ni<0 || m<=ni ||
           nj<0 || n<=nj ||
           ho[ni][nj])continue;
        G[i*n+j].pb(ni*n+nj);
      }
    }
  }

  rep(i,n*m){
    if(match[i]!=-1 || ho[i/n][i%n])continue;
    memset(vis,0,sizeof(vis));
    if(!augment(i)){
      cout<<"NO"<<endl;
      return 0;
    }
  }
  cout<<"YES"<<endl;
}