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

## WA的同学进，这题太恶心了！！

Posted by speedcell4 at 2011-08-17 16:25:21 on Problem 2446
```In the next k lines, there is a pair of integers (x, y) in each line, which represents a hole in the y-th row, the x-th column.

#include<iostream>
#define SIZE 33
using namespace std;
int t[SIZE][SIZE][2];
bool a[SIZE][SIZE][SIZE][SIZE],v[SIZE][SIZE];
int n,m,k,x,y;
int go[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool canGo(int x,int y)
{
return (x>=0&&y>=0)&&(x<n&&y<m);
}
bool find(int x,int y)
{
for(int i=0;4-i>0;i++)
{
int xx=x+go[i][0];
int yy=y+go[i][1];
if(canGo(xx,yy))
if(v[xx][yy]==false&&a[x][y][xx][yy]==true)
{
v[xx][yy]=true;
if((t[xx][yy][0]==-1&&t[xx][yy][1]==-1)||find(t[xx][yy][0],t[xx][yy][1]))
{
t[xx][yy][0]=x;
t[xx][yy][1]=y;
return true;
}
}
}
return false;
}
int findMatch(void)
{
int count=0;
for(int i=0;n-i>0;i++)
{
for(int j=0;m-j>0;j++)
{
if((i+j)%2==0) continue;
else
{
memset(v,false,sizeof(v));
if(find(i,j)) count++;
}
}
}
return count;
}
int main()
{
while(scanf("%d %d %d",&n,&m,&k)!=EOF)
{
memset(t,-1,sizeof(t));
memset(a,true,sizeof(a));
for(int i=0;k-i>0;i++)
{
scanf("%d %d",&y,&x);
x--;
y--;
if((x+y)%2==0)
{
for(int i=0;4-i>0;i++)
{
int xx=x+go[i][0];
int yy=y+go[i][1];
if(canGo(xx,yy)) a[xx][yy][x][y]=false;
}
}
else
{
for(int i=0;4-i>0;i++)
{
int xx=x+go[i][0];
int yy=y+go[i][1];
if(canGo(xx,yy)) a[x][y][xx][yy]=false;
}
}
}
if(k%2==1)
{
printf("NO\n");
continue;
}
if((2*findMatch()+k)==(m*n)) printf("YES\n");
else printf("NO\n");
}
return 0;
}```

Followed by: