1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 110 4 int n,m,k,edge[MAXN][MAXN][2],ans; 5 bool used[MAXN][MAXN],map[MAXN][MAXN],wat[MAXN][MAXN]; 6 int _1[]={0,0,0,-1,1},_2[]={0,1,-1,0,0};//记录四个方向  7 bool dfs(int x,int y) 8 { 9     for(int i=1;i<=4;i++)10     {11         int xi=x+_1[i],yi=y+_2[i];//v的横纵坐标 12         if(xi>n||yi>m||xi<1||yi<1)continue;//出界 13         if(wat[xi][yi]||map[xi][yi]||used[xi][yi])continue;14         used[xi][yi]=true;15         if(!edge[xi][yi][0]||dfs(edge[xi][yi][0],edge[xi][yi][1]))16         {17             edge[xi][yi][0]=x;edge[xi][yi][1]=y;//更新match 18             return true;19         }20     }21     return false;22 }23 int main()24 {25     scanf("%d%d",&n,&m);26     scanf("%d",&k);27     for(int i=1;i<=k;i++)28     {29         int t1,t2;30         scanf("%d%d",&t1,&t2);31         wat[t1][t2]=true;//判断是否是水格 32     }33     for(int i=1;i<=n;i++)34     {35         for(int j=1;j<=m;j++)36         {37             if(wat[i][j])continue;38             else if(i%2==j%2)map[i][j]=true;//分子集 39         }40     }41     for(int i=1;i<=n;i++)42     {43         for(int j=1;j<=m;j++)44         {45             if(!wat[i][j]&&map[i][j])46             {47                 memset(used,false,sizeof(used));48                 if(dfs(i,j))ans++;49             }50         }51     }52     printf("%d\n",ans);53     return 0;54 }