有一个n行m列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第i行第j列的格子只能参与m_i,j次交换。

第一行包含两个整数n，m（1<=n, m<=20）。以下n行为初始状态，每行为一个包含m个字符的01串，其中0表示黑色棋子，1表示白色棋子。以下n行为目标状态，格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串，表示每个格子参与交换的次数上限。

 

输出仅一行，为最小交换总次数。如果无解，输出-1。

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 typedef long long lnt;

 const int oo=0x3f3f3f3f;

 const int di[]={,,-,,,,-,-};

 const int dj[]={-,,,,-,,,-};

 struct pnt{

     int hd;

     int dis;

     int val;

     int pre;

     int lst;

     bool vis;

 }p[];

 struct ent{

     int twd;

     int lst;

     int vls;

     int dis;

 }e[];

 int cnt;

 int n,m;

 int s,t;

 int maxflow;

 int no[][];

 int st[][];

 int ed[][];

 int vl[][];

 std::queue<int>Q;

 void ade_(int f,int t,int v,int d)

 {

     cnt++;

     e[cnt].twd=t;

     e[cnt].vls=v;

     e[cnt].dis=d;

     e[cnt].lst=p[f].hd;

     p[f].hd=cnt;

     return ;

 }

 void adde(int f,int t,int v,int d)

 {

     ade_(f,t,v,d);

     ade_(t,f,,-d);

     return ;

 }

 bool Spfa(void)

 {

     while(!Q.empty())Q.pop();

     for(int i=;i<=t;i++)

     {

         p[i].dis=p[i].val=oo;

         p[i].pre=-;

         p[i].vis=false;

     }

     Q.push(s);

     p[s].vis=true;

     p[s].dis=;

     while(!Q.empty())

     {

         int x=Q.front();

         Q.pop();

         p[x].vis=false;

         for(int i=p[x].hd;i;i=e[i].lst)

         {

             int to=e[i].twd;

             if(p[to].dis>p[x].dis+e[i].dis&&e[i].vls)

             {

                 p[to].dis=p[x].dis+e[i].dis;

                 p[to].pre=x;

                 p[to].lst=i;

                 p[to].val=std::min(p[x].val,e[i].vls);

                 if(p[to].vis)continue;

                 p[to].vis=true;

                 Q.push(to);

             }

         }

     }

     return p[t].pre!=-;

 }

 int Ek(void)

 {

     int ans=;

     while(Spfa())

     {

         maxflow+=p[t].val;

         ans+=p[t].dis*p[t].val;

         for(int i=t;i!=s;i=p[i].pre)

         {

             e[p[i].lst].vls-=p[t].val;

             e[((p[i].lst-)^)+].vls+=p[t].val;

         }

     }

     return ans;

 }

 int main()

 {

     int a1(),a2();

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)for(int j=;j<=m;j++)no[i][j]=++cnt;

     s=cnt*+,t=s+;

     cnt=;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             scanf("%1d",&st[i][j]),a1+=st[i][j];

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             scanf("%1d",&ed[i][j]),a2+=ed[i][j];

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             scanf("%1d",&vl[i][j]);

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=m;j++)

         {

             if(!st[i][j])adde(s,no[i][j],,);

             if(!ed[i][j])adde(no[i][j],t,,);

             int frm,twd;

             if(st[i][j]==ed[i][j])frm=twd=vl[i][j]/;

             if(st[i][j]>ed[i][j])frm=(vl[i][j]+)/,twd=vl[i][j]/;

             if(st[i][j]<ed[i][j])twd=(vl[i][j]+)/,frm=vl[i][j]/;

             adde(no[i][j]+n*m,no[i][j],frm,);

             adde(no[i][j],no[i][j]+*n*m,twd,);

             for(int d=;d<;d++)

             {

                 int ii=di[d]+i;

                 int jj=dj[d]+j;

                 if(!no[ii][jj])continue;

                 adde(no[i][j]+*n*m,no[ii][jj]+m*n,oo,);

             }

         }

     }

     int ans=Ek();

     if(m*n-maxflow!=a1||a1!=a2)ans=-;

     printf("%d\n",ans);

     return ;

 }