hdu4678Mine

http://acm.hdu.edu.cn/showproblem.php?pid=4678

之前写了一并差集找连通块 貌似不对 比赛时写的dfs爆栈了 只好用bfs了

单独数字块  为1

空白+数字块 数字数%2+1

异或

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<stdlib.h>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define N 1010

 int dis[][] = {,,-,,,,,-,,,,-,-,,-,-};

 int n,m,k;

 int vis[N][N],o[N][N],f[N][N];

 struct node

 {

     int x,y;

 };

 int bfs(int x,int y)

 {

     queue<node>q;

     struct node st,sd;

     int num = ,i;

     st.x = x;

     st.y = y;

     vis[x][y] = ;

     q.push(st);

     while(!q.empty())

     {

         sd = q.front();

         int tx = sd.x;

         int ty = sd.y;

         q.pop();

         for(i =  ;i <  ; i++)

         {

             int dx = tx+dis[i][];

             int dy = ty+dis[i][];

             if(dx>=&&dx<n&&dy>=&&dy<m&&!vis[dx][dy])

             {

                 vis[dx][dy] = ;

                 if(!f[dx][dy]&&o[dx][dy])

                 num++;

                 st.x = dx;

                 st.y = dy;

                 if(!f[dx][dy]&&!o[dx][dy])

                 q.push(st);

             }

         }

     }

     if(num%==)

     return ;

     return ;

 }

 int main()

 {

     int i,j,t,kk=;

     scanf("%d",&t);

     while(t--)

     {

         kk++;

         scanf("%d%d%d",&n,&m,&k);

         for(i =  ; i <= n ; i++)

             for(j =  ; j  <= m ; j++)

             {

                 f[i][j] = ;

                 o[i][j] = ;

                 vis[i][j] = ;

             }

         while(k--)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             f[x][y] = ;

             for(i =  ; i <  ; i++)

             {

                 int tx = x+dis[i][];

                 int ty = y+dis[i][];

                 if(tx>=&&tx<n&&ty>=&&ty<m)

                 o[tx][ty] = ;

             }

         }

         int ans=;

         for(i =  ; i < n ; i++)

             for(j =  ; j < m ; j++)

             if(!f[i][j]&&!vis[i][j]&&o[i][j]==)

             {

                 int w = bfs(i,j);

                 ans ^= w;

             }

         for(i =  ; i < n ; i++)

             for(j =  ; j < m ; j++)

             if(!f[i][j]&&!vis[i][j]&&o[i][j])

             ans ^= ;

         printf("Case #%d: ",kk);

         if(ans==)

         printf("Fanglaoshi\n");

         else

         printf("Xiemao\n");

     }

     return ;

 }