POJ 2446 Chessboard

要求用占两格的长方形铺满平面上除去指定点

二分图匹配

 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dx[]={,-,,};
int dy[]={,,,-};
int map[][];
int vis[][];
int link[*];
int m,n,k;
bool check(int x,int y)
{
return <=x&&x<m&&<=y&&y<n;
}
bool dfs(int t)
{
int nx,ny,nxt;
for(int i=;i<;i++)
{
nx=t/n+dx[i];
ny=t%n+dy[i];
if(check(nx,ny)&&!map[nx][ny]&&!vis[nx][ny])
{
vis[nx][ny]=;
nxt=nx*n+ny;
if(link[nxt]==-||dfs(link[nxt]))
{
link[nxt]=t;
return ;
}
}
}
return ;
}
int main()
{
int a,b;
while(~scanf("%d%d%d",&m,&n,&k))
{
memset(map,,sizeof(map));
for(int i=;i<k;i++)
{
scanf("%d%d",&b,&a);
a--; b--;
map[a][b]=;
}
int ans=;
memset(link,-,sizeof(link));
for(int i=;i<m;i++)
{
for(int j=;j<n;j++)
{
memset(vis,,sizeof(vis));
if(!map[i][j] && dfs(i*n+j)) ans++;
}
}
if(ans==n*m-k) puts("YES");
else puts("NO");
}
}
上一篇:.NET ORM框架(一)


下一篇:Bootstrap-CL:面包屑导航