| ||||||||||
| 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 | |||||||||
我找了很多的测试数据,都过了,可提交总是wa,哪位大牛帮我找找错呀,感激不尽。。。 一些测试数据#include<stdio.h>
#include<string.h>
struct node
{
int index;
int color;
}map[35][35];
int borad[520][520],vist[520],pipei[520],count0,count1,m,n;
int dian(int i,int j)
{
if(i>=1&&i<=m&&j>=1&&j<=n)
{
return 1;
}
else
{
return 0;
}
}
int dfs(int u)
{
int v;
for(v=0;v<count1;v++)
{
if(vist[v]==0&&borad[u][v]>0)
{
vist[v]=1;
if(pipei[v]==-1||dfs(pipei[v]))
{
pipei[v]=u;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,k,ans,x,y;
for(;scanf("%d%d%d",&m,&n,&k)!=EOF;)
{
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
map[i][j].color=-1;
map[i][j].index=0;
}
}
for(i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
map[y][x].color=2;
}
count0=0;
count1=0;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if((i+j)%2==1&&map[i][j].color!=2)
{
map[i][j].color=1;
map[i][j].index=count1;
count1++;
}
if((i+j)%2==0&&map[i][j].color!=2)
{
map[i][j].color=0;
map[i][j].index=count0;
count0++;
}
}
}
/*printf("%d %d\n",count0,count1);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
printf("-%d %d- ",map[i][j].color,map[i][j].index);
}
printf("\n");
}*/
if(count0!=count1)
{
printf("NO\n");
// return 0;
continue;
}
memset(borad,0,sizeof(borad));
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if((i+j)%2==0)
{
if(dian(i+1,j)&&map[i+1][j].color!=2)
{
borad[map[i][j].index][map[i+1][j].index]=1;
}
if(dian(i-1,j)&&map[i-1][j].color!=2)
{
borad[map[i][j].index][map[i-1][j].index]=1;
}
if(dian(i,j+1)&&map[i][j+1].color!=2)
{
borad[map[i][j].index][map[i][j+1].index]=1;
}
if(dian(i,j-1)&&map[i][j-1].color!=2)
{
borad[map[i][j].index][map[i][j-1].index]=1;
}
}
}
}
/*for(i=0;i<count0;i++)
{
for(j=0;j<count0;j++)
{
printf("%d ",borad[i][j]);
}
printf("\n");
}*/
memset(pipei,-1,sizeof(pipei));
ans=0;
for(i=0;i<count0;i++)
{
memset(vist,0,sizeof(vist));
if(dfs(i)) ans++;
}
if(ans==count0)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
4 4 3
1 4
2 1
4 2
4 4 2
1 4
4 2
8 8 1
4 5
12 27 3
1 1
5 5
3 4
12 27 0
3 3 3
2 2
1 2
2 3
5 5 9
3 4
2 3
3 3
4 5
2 2
1 1
4 4
2 4
5 4
30 30 12
23 24
2 4
3 5
4 19
18 3
3 4
8 3
3 5
3 6
10 30
10 29
15 15
5 6 17
1 2
2 2
3 2
4 2
5 2
6 2
1 3
2 3
3 3
4 3
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator