首先是一个常见套路：将棋子的交换等价为棋子的移动——这很重要。我们不妨把交换看做黑子的移动。
那么我们考虑这个问题的弱化版：假设每个格子的移动次数没有限制，该怎么做。
很显然将每个格子拆成两个点，然后每个右点向相邻的左点连边，跑最大流即可。
对于一个黑子的移动，我们发现，如果一个格子是这个黑子中途经过的点，那么这个格子必然会消耗两次交换次数。
故而，我们给从左点到右点的边设置一个容量上限，其值为交换次数上限的一半。
但是这么做的话我们发现了一个问题：倘若一个点起始状态和结束状态不一样，这个模型是无法有效描述结果的。
这是因为，如果一个点的起始状态和结束状态不一样，那么它通过的次数必然是奇数。
我们考虑这样拆点：将每个点拆成左，中，右三个点。然后，将每个点的右点向它的所有相邻点的左点连边，流量1，费用0。表示某个棋子走向了它的另一个相邻的棋子。
从中点向右点连一条边，表示这个点移出去的次数。显然，如果最终情况是白的而初始情况是黑的，这个点应该会多移出去一次。
从左点向中点连一条边，表示这个点移进来的次数。显然，如果最终情况是黑的而初始情况是白的，这个点应该会多移进来一次。
我们考虑这个「多移进来」和「多移出去」对这个点可以参与的交换次数的影响。
假若限定次数是偶数，那么多出来的这一次移动将使得这个点能参与的交换次数少一次；倘若限定次数是奇数，那么多出来的这一次移动将不影响这个点能参与的交换次数。
所以，我们可以用形如\(\lfloor \frac{limit+[end>begin]}{2} \rfloor \)和\(\lfloor \frac{limit+[begin>end]}{2} \rfloor \)的式子来描述这两条边的流量。
然后，对于题目要求的最小交换次数，我们考虑将原来就存在的连边加上费用。这样就满足了题目的要求。
#include<iostream>
#include<cstdio>
#include<queue>
const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={1,0,-1,1,-1,1,0,-1};
const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
return A<B?A:B;
}
struct ee{
int v;
int w;
int c;
int nxt;
}e[200005];
int h[1205],et=-1;
inline void Eadd(int U,int V,int W,int C){
e[++et]=(ee){V,W,C,h[U]};
h[U]=et;
}
inline void add(int U,int V,int W,int C){
Eadd(U,V,W,C);
Eadd(V,U,0,-C);
}
int n,m,s,t,vis[1205],dis[1205],val[1205],fa[1205],nw[1205];
std::queue<int> q;
inline bool SPFA(){
for(int i=1;i<=t;++i){
vis[i]=0,dis[i]=INF,val[i]=INF;
}
vis[s]=1,dis[s]=0,fa[t]=-1;
q.push(s);
int p;
while(!q.empty()){
p=q.front();
q.pop();
vis[p]=0;
for(int i=h[p];i>=0;i=e[i].nxt){
if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
dis[e[i].v]=dis[p]+e[i].c;
fa[e[i].v]=p;
nw[e[i].v]=i;
val[e[i].v]=Min(e[i].w,val[p]);
if(!vis[e[i].v]){
vis[e[i].v]=1;
q.push(e[i].v);
}
}
}
}
return fa[t]!=-1;
}
int answ=0,ansc=0;
inline void zkw(){
int p;
while(SPFA()){
p=t;
answ+=val[t];
ansc+=val[t]*dis[t];
while(p!=s){
e[nw[p]].w-=val[t];
e[nw[p]^1].w+=val[t];
p=fa[p];
}
}
}
char begin[25][25],end[25][25],limit[25][25];
inline int calc(int X,int Y,int T){
return T*n*m+(X-1)*m+Y;
}
void init(){
scanf("%d%d",&n,&m);
s=3*n*m+1,t=3*n*m+2;
int cnt=0;
for(int i=1;i<=t;++i){
h[i]=-1;
}
for(int i=1;i<=n;++i){
std::cin>>begin[i]+1;
}
for(int i=1;i<=n;++i){
std::cin>>end[i]+1;
}
for(int i=1;i<=n;++i){
std::cin>>limit[i]+1;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(begin[i][j]=='1'){
++cnt;
add(s,calc(i,j,1),1,0);
}
add(calc(i,j,1),calc(i,j,2),(limit[i][j]-'0'+(int)(begin[i][j]>end[i][j]))>>1,1);
if(end[i][j]=='1'){
add(calc(i,j,1),t,1,0);
}
add(calc(i,j,0),calc(i,j,1),(limit[i][j]-'0'+(int)(end[i][j]>begin[i][j]))>>1,1);
for(int k=0;k<8;++k){
int x=i+dx[k],y=j+dy[k];
if(x>=1&&x<=n&&y>=1&&y<=m){
//n,m!!!
add(calc(i,j,2),calc(x,y,0),INF,0);
}
}
}
}
zkw();
printf("%d\n",(answ==cnt?ansc:-1)>>1);
}
int main(){
init();
return 0;
}