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 |
whd#include <stdio.h> #include <math.h> int r[6000] , n , m, n1, n2 , ans = 0 , b[110][110], dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0}, e ; char vi[6000] , q[110][110] ; typedef struct w{int a, b; }w; w w1[6000] , w2[6000] ; char find (int x) { int i ; for (i = 0; i < 4; i ++ ) if (w1[x].a + dx[i] >= 1 && w1[x].a + dx[i] <= n && w1[x].b + dy[i] >= 1 && w1[x].b + dy[i] <= n && b[w1[x].a + dx[i]][w1[x].b + dy[i]] != -1 && ! vi[b[w1[x].a + dx[i]][w1[x].b + dy[i]]]){ vi[ b[w1[x].a + dx[i]][w1[x].b + dy[i]]] = 1; if ( ! r[ b[w1[x].a + dx[i]][w1[x].b + dy[i]]] || find (r[ b[w1[x].a + dx[i]][w1[x].b + dy[i]]]) ){ r[ b[w1[x].a + dx[i]][w1[x].b + dy[i]]] = x ; return 1 ;}} return 0 ; } main () { int i ,j ,t , a, bb; scanf ("%d%d%d",&n, &e, &m ) ; memset (q, 0, sizeof (q) ) ; memset (r, 0, sizeof (r) ) ; memset (b, -1, sizeof (b) ) ; for (i = 0 ; i < m; i ++ ){ scanf("%d%d", &a, &bb) ; q[bb][a] = 1;} n1 = n2 = 0 ; for (i = 1 ; i <= n; i ++ ) for (j = 1; j <= e; j ++ ) if ( ! q[i][j]){ if ((i + j) % 2 ){ w1[ ++ n1].a = i; w1[n1].b = j ; b[i][j] = n1;} else{ w2[ ++ n2].a = i; w2[n2].b = j; b[i][j] = n2 ;}} for (i = 1; i <= n1; i ++ ){ memset (vi, 0, sizeof (vi) ) ; if (find (i) ) ans ++ ;} printf ("%s\n", n * e - m == ans * 2 ? "YES" : "NO") ; system ("pause") ; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator