Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

whd

Posted by 117474335 at 2010-10-18 13:40:31 on Problem 2446
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator