一张残缺的棋盘,用1*2的矩形去覆盖它,要求矩形不互相重叠。
求矩形最多可以放多少个。
将棋盘染成黑白相间,黑色方格作为左边的点,白色方格作为右边的点,相邻的黑白方格中间连一条边。
对已经建好的图求最大匹配
#include<iostream> #include<cmath> using namespace std; #define MAXSIZE 34 int map[MAXSIZE][MAXSIZE]; int vis[MAXSIZE][MAXSIZE]; int xc[]={0,0,1,-1}; int yc[]={1,-1,0,0}; int m,n,k; int num; typedef struct point{ int x; int y; }point; point isWho[MAXSIZE*MAXSIZE]; int dfs(int x,int y) { for(int k=0;k<4;k++)//遍历四个方向的点 { int xt=x+xc[k]; int yt=y+yc[k]; if(map[xt][yt]==0) if(xt>=1&&yt>=1&&xt<=m&&yt<=n&&!vis[xt][yt])//在地图中 并且没有拜访过 { vis[xt][yt]=1; int temp=(xt-1)*32+yt; if((isWho[temp].x==-1&&isWho[temp].y==-1)||dfs(isWho[temp].x,isWho[temp].y))//没有人要 或者可以腾出来 { isWho[temp].x=x; isWho[temp].y=y; return 1; } } } return 0; } int main() { // freopen("in.txt","r",stdin); // while(scanf("%d%d%d",&m,&n,&k)!=EOF) { scanf("%d%d%d",&m,&n,&k); num=m*n; int i,j; memset(map,0,sizeof(map)); memset(isWho,-1,sizeof(isWho)); if((num-k)%2) { printf("NO\n"); return 0; } for(i=1;i<=k;i++) { int r,c; scanf("%d%d",&c,&r); map[r][c]=1; } int ans=0; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if((i+j)%2) { memset(vis,0,sizeof(vis));//清空 if(map[i][j]==0) if(dfs(i,j)) ans++; } } } // cout<<ans<<endl; if(ans*2==num-k) printf("YES\n"); else printf("NO\n"); } return 0; }
相关推荐
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ初级-图算法 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
北大POJ1159-Palindrome 解题报告+AC代码
poj 1000-3000部分代码 网上收集
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
北大POJ1159-Palindrome
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk