| ||||||||||
| 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 | |||||||||
出来吼吼。。。这题做的郁闷。。。贴代码。。。仅供参考。。
#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator