#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<vector>using namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pr;const double pi=acos(-1);#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define Rep(i,u) for(int i=head[u];i;i=Next[i])#define clr(a) memset(a,0,sizeof(a))#define pb push_back#define mp make_pair#define fi first#define sc second#define pq priority_queue#define pqb priority_queue <int, vector<int>, less<int> >#define pqs priority_queue <int, vector<int>, greater<int> >#define vec vector#define T 10001ld eps=1e-9;ll pp=1000000007;ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }//void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};ll read(){ ll ans=0; char last=‘ ‘,ch=getchar();while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar();while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar();if(last==‘-‘)ans=-ans; return ans;}#define M 500005#define N 50005const int INF=1<<30;int head[N],level[N],q[N],e,n,m;struct E_node{    int v,f,Next;}edge[M];int Map[1005][1005];void add(int x,int y,int z){    edge[++e].v=y; edge[e].f=z; edge[e].Next=head[x]; head[x]=e;    edge[++e].v=x; edge[e].f=0; edge[e].Next=head[y]; head[y]=e;}int bfs(int s,int t){    memset(level,0,sizeof(level));    level[s]=1;    int h=0,t_=1; q[h]=s;    while (h<t_){        int x=q[h++];        if (x==t) return 1;        for (int i=head[x];i;i=edge[i].Next){            int v=edge[i].v,f=edge[i].f;            if (!level[v] && f>0){                level[v]=level[x]+1;                q[t_++]=v;            }        }    }    return 0;}int dfs(int u,int maxf,int t){    if (u==t) return maxf;    int ret=0;    for (int i=head[u];i;i=edge[i].Next){        int v=edge[i].v,f=edge[i].f;        if (level[v]==level[u]+1 && f>0){            int Min=min(maxf-ret,f);            f=dfs(v,Min,t);            edge[i].f-=f;            edge[i^1].f+=f;            ret+=f;            if (ret==maxf) return ret;        }    }    return ret; }int Dinic(int s,int t){    int ans=0;    while (bfs(s,t)) ans+=dfs(s,INF,t);    return ans;}void build(){    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        {            if(Map[i][j]==1)            add(0,(i-1)*m+j,INF);            if(Map[i][j]==2)            add((i-1)*m+j,T,INF);            for(int k=1;k<=4;k++)            {                int nowi=i+dx[k],nowj=j+dy[k];                if(nowi<1||nowi>n||nowj>m||nowj<1||Map[i][j]==2) continue;                if(Map[i][j]!=1||Map[nowi][nowj]!=1)                {                        cout<<(i-1)*m+j<<‘ ‘<<(nowi-1)*m+nowj<<endl;                    add((i-1)*m+j,(nowi-1)*m+nowj,1);                }            }                        }}int main(){        n=read(),m=read();    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            scanf("%d",&Map[i][j]);    build();            printf("%d\n",Dinic(0,T));    return 0;}

#include<iostream>#include<cstdio>#include<cstring>#define inf 0x7fffffff#define T 10001using namespace std;int head[10005],q[10005],h[10005];int cnt=1,ans,n,m;int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0},mp[105][105];struct data{int to,next,v;}e[500001];void ins(int u,int v,int w){e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}void insert(int u,int v,int w){ins(u,v,w);ins(v,u,0);}bool bfs(){     int t=0,w=1,i,now;     memset(h,-1,sizeof(h));     q[0]=0;h[0]=0;     while(t<w)     {               now=q[t];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;                       }               }    return h[T]==-1? 0:1; }int dfs(int x,int f){    if(x==T)return f;    int w,used=0,i;    i=head[x];    while(i)    {            if(e[i].v&&h[e[i].to]==h[x]+1)            {                                          w=f-used;                                          w=dfs(e[i].to,min(w,e[i].v));                                          e[i].v-=w;                                          e[i^1].v+=w;                                          used+=w;                                          if(used==f)return f;                                          }            i=e[i].next;            }    if(!used)h[x]=-1;    return used;}void dinic(){while(bfs())ans+=dfs(0,inf);}void ini(){     scanf("%d%d",&n,&m);     for(int i=1;i<=n;i++)         for(int j=1;j<=m;j++)             scanf("%d",&mp[i][j]);     }void build(){    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        {            if(mp[i][j]==1)            insert(0,(i-1)*m+j,inf);            if(mp[i][j]==2)            insert((i-1)*m+j,T,inf);            for(int k=0;k<4;k++)            {                int nowi=i+xx[k],nowj=j+yy[k];                if(nowi<1||nowi>n||nowj>m||nowj<1||mp[i][j]==2) continue;                if(mp[i][j]!=1||mp[nowi][nowj]!=1)                {                    cout<<(i-1)*m+j<<‘ ‘<<(nowi-1)*m+nowj<<endl;                    insert((i-1)*m+j,(nowi-1)*m+nowj,1);                }            }                        }}int main(){    ini();    build();    dinic();    printf("%d",ans);    return 0;    }