题意;除了所给的一些点外,问能不能用1*2的矩形覆盖所有的点,矩形间不能重叠。
思路:简单二分匹配,,,,,,,
#include<stdio.h>
#include<string.h>
const int N=1200;
int match[N],link[N],map[35][35],n,m;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int find(int u)
{
int i,v,x,y,X,Y;
x=u/m;y=u%m;
for(i=0;i<4;i++)
{
X=x+dir[i][0];
Y=y+dir[i][1];
if(X<0||X>=n||Y<0||Y>=m||map[X][Y]==1)continue;
v=X*m+Y;
if(link[v]==0)
{
link[v]=1;
if(match[v]==-1||fi......
阅读全文