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

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

Posted by wangfang20 at 2012-09-05 11:11:54 on Problem 2446
In Reply To:WA的同学进，这题太恶心了！！ Posted by:speedcell4 at 2011-08-17 16:25:21
```> 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.
> 注意这句话……汗……
> 附16MS代码：
> #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: