题意:给你一个n*m方格 让你用1*2的的小方格去铺满,其中有k个方格不能被铺到。
思路:二分图建图, 以每个格子为点建图,如果可以用一块1*2的小方格铺到,就连一条边。
每个格子在X集合和Y集合都有一个点,只要任意一边被匹配到了就算可以,然后就是二分图匹配了。
上代码。
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<vector> #include<stack> #include<math.h> #define maxn 32*32+5 using namespace std; vector<int> G[maxn]; int macx[maxn]; int macy[maxn]; bool check[maxn]; int N; void init() { for(int i=0;i<N;i++) G[i].clear(); } void add_edge(int from,int to) { G[from].push_back(to); } bool dfs(int u) { for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!check[v]) { check[v]=1; if((macy[v]==-1&&macx[v]==-1)) { macx[u]=v; macy[v]=u; macy[u]=-1; macx[v]=-1; return 1; } else if(macy[v]==-1&&dfs(macx[v])) { macx[u]=v; macy[v]=u; macy[u]=-1; macx[v]=-1; return 1; } else if(macx[v]==-1&&dfs(macy[v])) { macx[u]=v; macy[v]=u; macy[u]=-1; macx[v]=-1; return 1; } } } return 0; } int xyl() { memset(macx,-1,sizeof(macx)); memset(macy,-1,sizeof(macy)); int ans=0; for(int i=0;i<N;i++) { if(macx[i]==-1&&macy[i]==-1) { memset(check,0,sizeof(check)); if(dfs(i)) { //printf("%d\n",i); ans++; } } } return ans; } bool mp[50][50]; int x[4]={1,0,-1,0}; int y[4]={0,1,0,-1}; int main() { int n,m,k; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { int k1=k; memset(mp,0,sizeof(mp)); while(k1--) { int A,B; scanf("%d%d",&A,&B); mp[B-1][A-1]=1; } if((n*m-k)%2==1) { printf("NO\n"); continue; } N=n*m; init(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { int p=i*m+j; if(mp[i][j]==1) continue; for(int k=0;k<4;k++) { int nx=i+x[k]; int ny=j+y[k]; if(nx>=0&&ny>=0&&nx<n&&ny<m&&mp[nx][ny]==0) { int p1=nx*m+ny; add_edge(p,p1); } } } int ans=xyl(); int p=(n*m-k)/2; //printf("%d\n",ans); if(ans==p) printf("YES\n"); else printf("NO\n"); } }
原文:http://blog.csdn.net/u012896700/article/details/25627805