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