1 /* CODEVS1022 */  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <cmath>  6   7 #define maxn 10008  8   9 struct edge{ 10     int u,v,next; 11 }eg[maxn*4]; 12  13 int dx[4]={0,0,1,-1}; 14 int dy[4]={1,-1,0,0}; 15 int a[108][108]; 16 int cl[maxn]; 17 int n,m,k,sum,ans; 18 int last[maxn],l[maxn]; 19 bool pd[maxn]; 20  21 void dfs(int i,int j,int w) 22 { 23     int x,y,k; 24     cl[a[i][j]]=w; 25     for (k=0;k<4;k++) 26     { 27         int x,y; 28         x=i+dx[k]; 29         y=j+dy[k]; 30         if ((a[x][y]!=-1)&&!cl[a[x][y]]) 31             dfs(x,y,3-w); 32     }         33 } 34 void add(int u,int v) 35 { 36     eg[++sum].u=u; 37     eg[sum].v=v; 38     eg[sum].next=last[u]; 39     last[u]=sum; 40 } 41 bool find(int u) 42 { 43     for (int i=last[u];i;i=eg[i].next) 44     { 45         int v=eg[i].v; 46         if (!pd[v]) 47         { 48             pd[v]=1; 49             if ((!l[v])||find(l[v])) 50             { 51                 l[v]=u; 52                 return 1; 53             } 54         } 55     } 56     return 0; 57 } 58 int main() 59 { 60     int i,j,k; 61     sum=0; 62     memset(a,-1,sizeof(a)); 63     scanf("%d%d%d",&m,&n,&k); 64     for (i=1;i<=m;i++) 65         for (j=1;j<=n;j++) 66             a[i][j]=(i-1)*n+j; 67     for (int i=1;i<=k;i++) 68     { 69         int x,y; 70         scanf("%d",&x); 71         if (x==0) break; 72         scanf("%d",&y); 73         a[x][y]=-1; 74     }     75     for (i=1;i<=m;i++) 76         for (j=1;j<=n;j++) 77         if ((a[i][j]!=-1)&&!cl[a[i][j]]) 78             dfs(i,j,1); 79     for (i=1;i<=m;i++) 80         for (j=1;j<=n;j++) 81             if (cl[a[i][j]]) for (k=0;k<4;k++) 82             { 83                 int x,y; 84                 x=i+dx[k]; 85                 y=j+dy[k]; 86                 if ((a[x][y]!=-1)&&cl[a[x][y]]) 87                     add(a[i][j],a[x][y]); 88             }     89     ans=0;     90     memset(l,0,sizeof(l)); 91     for (i=1;i<=m*n;i++) 92         if (cl[i]==1) 93         { 94             memset(pd,0,sizeof(pd)); 95             if (find(i)) ans++; 96         } 97     //for (i=1;i<=m*n;i++) printf("%d ",l[i]); 98     printf("%d",ans); 99     return 0;100 }