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

出来吼吼。。。这题做的郁闷。。。贴代码。。。仅供参考。。

Posted by 351200 at 2012-03-08 19:42:55 on Problem 2446
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;
const int MAXN=50 ;

struct node
{
    int x,y ;
};
node link[MAXN][MAXN] ;
int map[MAXN][MAXN] ;
int visit[MAXN][MAXN] ;
int k,m,n ;
int move[4][2]={0,-1,0,1,1,0,-1,0 } ;

int path(int tx,int ty)
{
    for(int i=0 ;i<4 ;i++)
    {
        int cx=tx+move[i][0] ;
        int cy=ty+move[i][1] ;
        if(cx>=1 && cx<=n && cy>=1 && cy<=m)
        {
            if(!map[cx][cy] && !visit[cx][cy])
            {
                visit[cx][cy]=1 ;
                if((link[cx][cy].x==-1&&link[cx][cy].y==-1)||path(link[cx][cy].x,link[cx][cy].y))
                {
                    link[cx][cy].x=tx ;
                    link[cx][cy].y=ty ;
                    return 1 ;
                }
            }
        }
    }
    return 0 ;
}
int MaxMatch()
{
    memset(link,-1,sizeof(link)) ;
    int res=0 ;
    for(int i=1 ;i<=n;i++)
     for(int j=1 ;j<=m ;j++)
     {
         if(!map[i][j])
         {
               if((i+j)%2==1)
               {
                  memset(visit,0,sizeof(visit)) ;
                  if(path(i,j))
                     res++ ;
               }
         }
     }
     if(res*2+k==m*n)
        return 1 ;
     else
        return 0 ;
}
int main()
{
   // freopen("in.txt","r",stdin) ;
    while(cin>>n>>m>>k)
    {
        if((m*n-k)%2==1)
           cout<<"NO"<<endl;
        else
        {
            memset(map,0,sizeof(map)) ;
            for(int i=0 ;i<k ;i++)
            {
                int cx,cy ;
                cin>>cy>>cx ;
                map[cx][cy]=1 ;
            }
            if(MaxMatch())
              cout<<"YES"<<endl;
            else
              cout<<"NO"<<endl ;
        }
    }
    return 0;
}

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