学步园

#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 99999999
#define T 10001
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct edge{
    int to,next,v;
}e[200001];
const int xx[4]={-1,0,1,0},yy[4]={0,-1,0,1};
int n,m,cnt=1,ans,head[10005],h[10005],map[101][101];
void insert(int u,int v,int w){
    e[++cnt]=(edge){v,head[u],w};
    head[u]=cnt;
}
void ins(int u,int v,int w){
    insert(u,v,w);
    insert(v,u,0);
}
bool bfs(){
    int q[10005],t=0,w=1;
    memset(h,-1,sizeof(h));
    q[0]=0;h[0]=0;
    while(t<w){
        int now=q[t++],i=head[now];
        while(i){
            if(e[i].v&&h[e[i].to]==-1){
                h[e[i].to]=h[now]+1;
                q[w++]=e[i].to;
            }
            i=e[i].next;
        }
    }
    if(h[T]==-1)return false;
    else return true;
}
int dfs(int x,int f){
    if(x==T)return f;
    int rest,used=0,i=head[x];
    while(i){
        if(e[i].v&&h[e[i].to]==h[x]+1){
            rest=f-used;
            rest=dfs(e[i].to,min(e[i].v,rest));
            e[i].v-=rest;
            e[i^1].v+=rest;
            used+=rest;
            if(used==f)return f;
        }
        i=e[i].next;
    }
    if(!used)h[x]=-1;
    return used;
}
void dinic(){
    while(bfs())ans+=dfs(0,inf);
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            map[i][j]=read();
    for(int i=1;i<=n;i++)  
        for(int j=1;j<=m;j++){
            if(map[i][j]==1) ins(0,(i-1)*m+j,inf);  
            else if(map[i][j]==2) ins((i-1)*m+j,T,inf);  
            for(int k=0;k<4;k++){
                int nowx=i+xx[k],nowy=j+yy[k];  
                if(nowx<1||nowx>n||nowy<1||nowy>m||map[i][j]==2)continue;  
                if(map[i][j]!=1||map[nowx][nowy]!=1)  
                ins((i-1)*m+j,(nowx-1)*m+nowy,1);  
            }      
        }
    dinic();
    printf("%d",ans);
    return 0;
}