| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
从早8点开始,WA到现在也没能找出原因来,希望有心人看看我的代码,指点一下迷津,感激涕零#include<stdio.h>
#include<memory.h>
#define N 36
#define init(a) memset(a,0,sizeof(a))
int x[N]={0,-1,0,1,0},y[N]={0,0,-1,0,1};
int G[N][N],used[N][N],link[N][N][2];
int n,row,col;
////////////////////////////////////黑白染色,如果数量不等则查找失败
int readData()
{
int i,j,k,t=0;
init(G);
for(i=1;i<=row;i++)
for(j=1;j<=col;j++)
if((i+j)%2) G[i][j]=1;
else G[i][j]=-1;
for(k=1;k<=n;k++) {
scanf("%d%d",&i,&j);
if(G[i][j]==1) t++;
G[j][i]=0;
}
if(2*t==n) return 1;
else return 0;
}
///////////////////////////////////////匈牙利算法求完美匹配
int dfs(int sx,int sy)
{
int i,j,k,tx,ty;
for(k=1;k<=4;k++){
i=sx+x[k],j=sy+y[k];
if(G[i][j]==-1&&!used[i][j]) {
used[i][j]=1;
tx=link[i][j][0],ty=link[i][j][1];
link[i][j][0]=sx,link[i][j][1]=sy;
if(!tx||dfs(tx,ty)) return 1;
link[i][j][0]=tx,link[i][j][1]=ty;
}
}
return 0;
}
int work()
{
int i,j;
init(link);
for(i=1;i<=row;i++)
for(j=1;j<=col;j++){
init(used);
if(G[i][j]==1&&!dfs(i,j)) return 0;//如果有一点无法被覆盖则查找失败
}
return 1;
}
int main()
{
// freopen("data.txt","r",stdin);
while(scanf("%d%d%d",&row,&col,&n)!=EOF) {
if(!readData()||(row*col-n)%2||!work())////////////黑白点总数为奇数则查找失败
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator