最小费用最大流。
题目涉及黑白棋子和两种状态，均考虑显然比较繁杂。暂且先不管白棋子和不变色的黑棋子，将所有初始状态就是黑棋子的点与源点相连，最终状态是黑棋子的点与汇点相连。因为黑棋子的交换可以看作移动，显然只有端点只交换了一次其他中间点交换了两次因此建边时流量应。
建边方式如下：
1）连源汇，流量，费用，表示有待匹配；
2）中间点，初始状态与最终状态相连，流量为交换次数，费用为；
3）初始状态与最终状态不同，且可交换次数为奇数的黑棋，单独向最终状态连一条边，流量，费用；
4）处理格点，向八个方向连边，流量，费用，即交换需要付出的代价。
跑模板即可。
注意：
1）依然是数组大小！
2）费用流基本上就是用 spfa 代替了 bfs ，每次通过 spfa 寻找到的最短路，再 dfs 不断增广。
3）数组是用来拆点的，连边的流量就相当于是交换次数。能成功交换的交换次数一定是偶数的，因此如果是奇数那就应该补上原本就有的那次交换。
- 设原来的交换次数，后为，实际上只会交换次，因此应该加边补上。
4）spfa 中的阶层直接由费用进行划分，由于是最短路初始值为，最终判断时也变为了是否等于
5）dfs 中增加了一个数组的判断操作，去掉会段错误（暂时不知道为什么
6）玄学弧优化，然而我的出锅了...
#include <bits/stdc++.h>
#define ll long long
#define maxn 5000
#define INF 1000000000000
using namespace std;
ll n,m,a[maxn][maxn],b[maxn][maxn],l[maxn][maxn];
ll si,ti;
ll s,t,p;
ll ff[15][3]={{0,1},{0,-1},{1,0},{-1,0},{-1,1},{1,-1},{1,1},{-1,-1}};
char c[maxn][maxn];
struct Node{
ll nx,to,dis,val;
}e[maxn<<2];
ll cnt=1,hd[maxn];
ll vit[maxn],dep[maxn],cur[maxn];
ll ansf,anss;
queue<ll>q;
inline ll mn(ll u,ll v){
return u<v?u:v;
}
inline ll read(){
ll x=0,f=0;char c=getchar();
while(!isdigit(c))
f|=c=='-',c=getchar();
while(isdigit(c))
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
inline void add(ll u,ll v,ll w,ll vl){
e[++cnt].to=v;
e[cnt].dis=w;
e[cnt].val=vl;
e[cnt].nx=hd[u];
hd[u]=cnt;
}
inline ll sm(ll u,ll v){
return (u-1)*m+v;
}
inline ll ct(ll u,ll v){
return (u-1)*m+v+n*m;
}
inline int spfa(){
for(register int i=1;i<=p;++i)
vit[i]=0,dep[i]=INF,cur[i]=hd[i];
q.push(s);
vit[s]=1,dep[s]=0;
while(!q.empty()){
ll u=q.front();q.pop();
vit[u]=0;
for(register int i=hd[u];i;i=e[i].nx){
ll to=e[i].to,val=e[i].val;
if(e[i].dis&&dep[to]>dep[u]+val){
dep[to]=dep[u]+val;
if(!vit[to]){
vit[to]=1;
q.push(to);
}
}
}
}
return (dep[t]!=INF);
}
inline ll dfs(ll u,ll limit){
if(u==t) return limit;
ll flow=0,fj;
vit[u]=1;
for(register int i=hd[u];i;i=e[i].nx){
ll to=e[i].to;
// cur[u]=i;
if((!vit[to]&&e[i].dis&&dep[u]+e[i].val==dep[to])&&(fj=dfs(to,mn(limit,e[i].dis)))>0){
e[i].dis-=fj;
e[i^1].dis+=fj;
flow+=fj;
limit-=fj;
if(!limit){
vit[u]=0;
break;
}
}
}
return flow;
}
int main(){
n=read();m=read();
s=t-1,p=t=2*n*m+2;
for(register int i=1;i<=n;++i){
cin>>c[i];
for(register int j=1;j<=m;++j)
a[i][j]=c[i][j-1]-'0',si+=(a[i][j]);
}
for(register int i=1;i<=n;++i){
cin>>c[i];
for(register int j=1;j<=m;++j)
b[i][j]=c[i][j-1]-'0',ti+=(b[i][j]);
}
if(si!=ti){
printf("-1\n");
return 0;
}
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
if(b[i][j]!=a[i][j])
if(a[i][j])
add(s,sm(i,j),1,0),
add(sm(i,j),s,0,0),
++ansf;
else
add(ct(i,j),t,1,0),
add(t,ct(i,j),0,0);
for(register int i=1;i<=n;++i){
cin>>c[i];
for(register int j=1;j<=m;++j){
l[i][j]=c[i][j-1]-'0';
add(sm(i,j),ct(i,j),l[i][j]>>1,0),
add(ct(i,j),sm(i,j),0,0);
if((a[i][j]^b[i][j])&&(l[i][j]&1))
add(sm(i,j),ct(i,j),1,0),
add(ct(i,j),sm(i,j),0,0);
for(register int k=0;k<=7;++k){
ll dx=i+ff[k][0];
ll dy=j+ff[k][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m)
add(ct(i,j),sm(dx,dy),INF,1),
add(sm(dx,dy),ct(i,j),0,-1);
}
}
}
while(spfa()){
ll tik=dfs(s,INF);
ansf-=tik,anss+=tik*dep[t];
// cout<<"我好困呜呜呜\n";
// cout<<"ans: "<<tik<<endl;
}
if(ansf) puts("-1");
else printf("%lld\n",anss);
return 0;
}
