{
if((i+j)&1)//奇点
map1[i][j]=++ln;
else//偶点
map1[i][j]=++rn;
}
else
map1[i][j]=0;
}
}
for(i=1;i<=ln;i++)
map[i].clear();
for(i=1;i<=rn;i++)
match[i]=-1;
//建二分图
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(!map1[i][j]||!((i+j)&1))
continue;
for(int k=0;k<4;k++)
{
x=i+dirt[k][0];
y=j+dirt[k] ;
if(x<=0||x>n||y<=0||y>m||!map1[x][y])
continue;
map[map1[i][j]].push_back(map1[x][y]);
}
}
//求最大匹配
ans=0;
for(i=1;i<=ln;i++)
{
for(j=1;j<=rn;j++)
fy[j]=0;
if(path(i))
ans++;
}
printf(“%d\n”,ln+rn-ans);
}
return 0;
}