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; }