Link：http://poj.org/problem?id=2446
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 14050 | Accepted: 4372 |
Description
We call a grid, which doesn’t contain a hole, a normal grid. Bob has to follow the rules below:
1. Any normal grid should be covered with exactly one card.
2. One card should cover exactly 2 normal adjacent grids.
Some examples are given in the figures below:
A VALID solution.
An invalid solution, because the hole of red color is covered with a card.
An invalid solution, because there exists a grid, which is not covered.
Your task is to help Bob to decide whether or not the chessboard can be covered according to the rules above.
Input
Output
Sample Input
4 3 2 2 1 3 3
Sample Output
YES
Hint
A possible solution for the sample input.
Source
My code：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=1111;
vector<int>map[maxn];
int id[33][33],match[maxn],cnt,ans,m,n,k;
bool vis[maxn],hole[33][33];
bool dfs(int u)
{
for(int i=0;i<map[u].size();i++)
{
if(!vis[map[u][i]])
{
vis[map[u][i]]=true;
if(match[map[u][i]]==-1||dfs(match[map[u][i]]))
{
match[map[u][i]]=u;
return true;
}
}
}
return false;
}
void hangry()
{
memset(match,-1,sizeof(match));
ans=0;
for(int i=1;i<=cnt;i++)
{
memset(vis,false,sizeof(vis));
if(dfs(i))
ans++;
}
}
int main()
{
int i,j,x,y;
while(scanf("%d%d%d",&m,&n,&k)==3)
{
memset(hole,false,sizeof(hole));
while(k--)
{
scanf("%d%d",&x,&y);
hole[y][x]=true;
}
if((m*n)&1)
{
printf("NO\n");
continue;
}
cnt=0;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(!hole[i][j])
{
id[i][j]=++cnt;
}
}
}
for(i=1;i<=cnt;i++)
map[i].clear();
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(!hole[i][j])
{
if(i-1>=1&&!hole[i-1][j])
{
map[id[i][j]].push_back(id[i-1][j]);
}
if(i+1<=m&&!hole[i+1][j])
{
map[id[i][j]].push_back(id[i+1][j]);
}
if(j-1>=1&&!hole[i][j-1])
{
map[id[i][j]].push_back(id[i][j-1]);
}
if(j+1<=n&&!hole[i][j+1])
{
map[id[i][j]].push_back(id[i][j+1]);
}
}
}
}
hangry();
if(ans==cnt)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
某大牛采用邻接表的方法，效率更高，以下来自：http://blog.chinaunix.net/uid-22263887-id-1778940.html
解题思路
题意：
玩个游戏：给出一个m行n列的棋盘，里面有m*n个方格，其中有k个格子上有洞，我们称那些没洞的格子叫正常的格子（normal grid）,Bob要遵循两个规则去玩： （1）任何一个正常的格子都要被一张卡覆盖，（卡片是1*2规格的） （2）一张卡要正好覆盖两个相邻的正常格子
我们的任务是帮助Bob决定是否棋盘在上述两个规则下能被覆盖。
思路：
因为棋盘上都是两个格子放一张卡片，所以到最后肯定是两个点两个点连着的。由此想到了二分匹配，具体是这样的：
给每个格子编号，从第一行到最后一行编号为1—12 ，然后每个点跟临近的正常点连接，这就建成了二分图，如右上图。
然后以此建邻接表，建表时，枚举每个点，如果是正常点i，那么与他相邻的正常点(v)的邻接点数增一（g[v][0]++），并使g[v][g[v][0]] = i;
然后就是二分匹配模版了，完后看匹配数是否等于正常格子数，即是否能构成完美匹配。
#include <stdio.h>
#include <string.h>
#define N 34
#define M N*N
int g[M][5], used[M], mat[M];
int match, m, n;
int find(int k)
{
int i, j;
for(i=1; i<=g[k][0]; i++)
{
j = g[k][i];
if(!used[j])
{
used[j] = 1;
if(!mat[j] || find(mat[j]))
{
mat[j] = k;
return 1;
}
}
}
return 0;
}
void hungary()
{
int i;
for(i=1; i<=m*n; i++)
{
if(g[i][0] != -1 && g[i][0] != 0)
{
match += find(i);
memset(used, 0, sizeof(used));
}
}
}
int main()
{
int i, j;
int k;
int x, y;
//freopen("in.txt", "r", stdin);
scanf("%d%d%d", &m, &n, &k);
for(i=1; i<=k; i++)
{
scanf("%d%d", &x, &y);
g[x+(y-1)*n][0] = -1;
}
for(i=1; i<=m*n; i++)
{
if(g[i][0] != -1)
{
//left
if((i-1)%n >= 1 && g[i-1][0] != -1)
g[i-1][++g[i-1][0]] = i;
//right
if(i%n != 0 && g[i+1][0] != -1)
g[i+1][++g[i+1][0]] = i;
//up
if((i-(i%n)) / n >= 1 && g[i-n][0] != -1)
g[i-n][++g[i-n][0]] = i;
//down
if((i-(i%n)+1) / n <= m && g[i+n][0] != -1)
g[i+n][++g[i+n][0]] = i;
}
}
match = 0;
hungary();
if(match == m*n-k)
printf("YES\n");
else printf("NO\n");
//printf("%d\n", match);
return 0;
}
静态邻接表模板：来自http://blog.csdn.net/hackbuteer1/article/details/7398008
//poj_2446
/*==================================================*\
| 二分图匹配（匈牙利算法DFS 实现）
| 邻接表方法来实现;
| 优点：实现简洁容易理解，适用于稠密图，DFS找增广路快。
| 找一条增广路的复杂度为O（E），最多找V条增广路，故时间复杂度为O（VE）
耗时：0MS
==================================================*/
#include<stdio.h>
#include<memory.h>
#define MAX 1089 //33*33
bool flag,visit[MAX]; //记录V2中的某个点是否被搜索过
int match[MAX]; //记录与V2中的点匹配的点的编号
int cnt; //二分图中左边、右边集合中顶点的数目
bool hole[MAX][MAX];
int id[MAX][MAX];
int head[MAX];
struct edge
{
int to,next;
}e[100005];
int index;
void addedge(int u,int v)
{ //向图中加边的算法，注意加上的是有向边
//u为v的后续节点既是v---->u
e[index].to=v;
e[index].next=head[u];
head[u]=index;
index++;
}
// 匈牙利（邻接表）算法
bool dfs(int u)
{
int i,v;
for(i = head[u]; i != 0; i = e[i].next)
{
v = e[i].to;
if(!visit[v]) //如果节点v与u相邻并且未被查找过
{
visit[v] = true; //标记v为已查找过
if(match[v] == -1 || dfs(match[v])) //如果i未在前一个匹配M中，或者i在匹配M中，但是从与i相邻的节点出发可以有增广路径
{
match[v] = u; //记录查找成功记录，更新匹配M（即“取反”）
return true; //返回查找成功
}
}
}
return false;
}
int MaxMatch()
{
int i,sum=0;
memset(match,-1,sizeof(match));
for(i = 1 ; i <= cnt ; ++i)
{
memset(visit,false,sizeof(visit)); //清空上次搜索时的标记
if( dfs(i) ) //从节点i尝试扩展
{
sum++;
}
}
return sum;
}
int main(void)
{
int i,j,k,m,n,ans,y,x;
while (scanf("%d %d %d",&m,&n,&k)!=EOF)
{
memset(hole,false,sizeof(hole));
for (i = 1; i <= k; ++i)
{
scanf("%d %d",&y,&x);
hole[x][y] = true;
}
if((m*n-k)&1) //奇偶剪枝
{
puts("NO");
continue;
}
cnt = 0;
index = 1;
for (i = 1; i <= m; ++i)
{
for (j = 1; j <= n; ++j)
{
if(hole[i][j] == false) //对没有涂黑的点进行标号
{
id[i][j] = ++cnt;
}
}
}
memset(head,0,sizeof(head)); //切记要初始化
for (i = 1; i <= m; ++i)
{
for (j = 1; j <= n; ++j)
{
if(hole[i][j] == false)
{
if(i-1>0 && hole[i-1][j] == false) //建图。。要注意边界问题
addedge(id[i][j],id[i-1][j]);
if(i+1<=m && hole[i+1][j] == false)
addedge(id[i][j],id[i+1][j]);
if(j-1>0 && hole[i][j-1] == false)
addedge(id[i][j],id[i][j-1]);
if(j+1<=n && hole[i][j+1] == false)
addedge(id[i][j],id[i][j+1]);
}
}
}
ans = MaxMatch();
if (ans == cnt)
puts("YES");
else
puts("NO");
}
return 0;
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
