POJ 2446 Chessboard

問題

nxmマスのグリッドがある。
グリッド上にはいくつかの穴があいている。

グリッドに1x2の板を、穴の上を避けて、かつ穴以外の全てのマスを覆うように敷き詰めたい。

それが可能であるかどうか、判定せよ。

制約条件

n,m≦32

方針

各マスを頂点とし、マスとマスに隣接関係があるとき、対応する頂点同士に辺を張ったグラフを考える。
板の敷き詰め方を求めることは、このグラフ上の完全マッチングを求めることに対応している。

このグラフは二部グラフである（チェスのように市松模様に塗ったとき、白と黒のマスしか隣接しない）
したがって、マッチングには二部グラフの最大マッチングのアルゴリズムが使える。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int n,m,k;
bool hole[32][32];
vector<vi> e;

int p[1024];
bool v[1024];

bool match(int s){
  if(s<0)return 1;
  fr(i,e[s])if(!v[*i]){
    v[*i]=1;
    if(match(p[*i]))return p[*i]=s,p[s]=*i,1;
  }
  return 0;
}
int main(){
  scanf("%d%d%d",&n,&m,&k);
  rep(i,k){
    int x,y; scanf("%d%d",&x,&y);
    hole[y-1][x-1]=1;
  }
  e.resize(n*m);
  rep(i,n)rep(j,m)if(!hole[i][j]){
    rep(d,4){
      int y=i+dy[d], x=j+dx[d];
      if(y<0||x<0||y>=n||x>=m||hole[y][x])continue;
      e[y*m+x].pb(i*m+j);
    }
    p[i*m+j]=-1;
  }
  
  int ans=0;
  rep(i,n)rep(j,m)if(!hole[i][j]&&(i+j)%2==0){
    rep(k,n*m)v[k]=0;
    if(match(i*m+j))ans++;
  }
  puts(ans*2==n*m-k?"YES":"NO");
  
  return 0;
}