对于这种题很容易看出是费用流吧……
但这道题不容易建模；
首先是怎么表示目标状态和其实状态，看起来有黑有白很复杂
但实际上，不难发现，白色格子没什么用，起决定作用的是黑格子
也就是我们可以把问题简化：我们怎么把开始的黑格子移到目标位置
但这个移动不是一般的移动；
在一条路径中，不难发现，起始两点是只要交换一次，其他路径上个点都是要交换2次
由于题目给出的限制是点的交换次数限制c，所以不难想到要拆点
但是平常的拆两点好像无法表示这个特征，
于是我们就拆成3个点……
p1--->p0--->p2
p1表示交换进来，p2表示交换出去；
所以不难得出：
对于每个点，如果它是原图中的黑点，连边<p1,p0,c/2,0>，<p0,p2,(c+1)/2,0>，<s,p0,1,0>；
如果它是新图中的黑点，连边<p1,p0,(c+1)/2>，<p0,p2,c/2,0>，<p0,t,1,0>；
注意存在有的点在新图原图都是黑点的情况（在这里WA了一次）
如果它在两个图中都是白点，那么连边<p1,p0,c/2,0>，<p0,p2,c/2,0>
最后对于原图中任意可达两点，连边<pi2,pj1,inf,1>
注意这道题可以交换对角线，还要判断是否可行，细节挺多
const dx:array[..] of integer=(-,,,,,-,-,);
dy:array[..] of integer=(,,,-,,-,,-);
inf=;
type node=record
next,point,cost,flow:longint;
end; var edge:array[..] of node;
p,pre,cur,d:array[..] of longint;
v:array[..] of boolean;
a,b,c:array[..,..] of integer;
q:array[..] of longint;
ch,t,n,m,i,j,k,x,y,po,tot,sum,ans,len:longint;
s:string; procedure add(x,y,f,w:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].cost:=w;
edge[len].next:=p[x];
p[x]:=len;
end; function spfa:boolean;
var i,x,y,f,r:longint;
begin
fillchar(v,sizeof(v),false);
v[]:=true;
for i:= to t do
d[i]:=inf;
d[]:=;
f:=;
r:=;
q[f]:=;
while f<=r do
begin
x:=q[f];
v[x]:=false;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if edge[i].flow> then
if d[y]>d[x]+edge[i].cost then
begin
d[y]:=d[x]+edge[i].cost;
pre[y]:=x;
cur[y]:=i;
if not v[y] then
begin
inc(r);
q[r]:=y;
v[y]:=true;
end;
end;
i:=edge[i].next;
end;
inc(f);
end;
if d[t]=inf then exit(false) else exit(true);
end; procedure mincost;
var i,j,neck:longint;
begin
while spfa do
begin
i:=t;
neck:=inf;
while i<> do
begin
j:=cur[i];
if neck>edge[j].flow then neck:=edge[j].flow;
i:=pre[i];
end;
i:=t;
while i<> do
begin
j:=cur[i];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
i:=pre[i];
end;
ans:=ans+d[t]*neck;
dec(ch,neck);
if ch= then break;
end;
end; begin
readln(n,m);
len:=-;
fillchar(p,sizeof(p),);
t:=*n*m+;
for i:= to n do
begin
readln(s);
for j:= to m do
begin
a[i,j]:=ord(s[j])-;
tot:=tot+a[i,j];
end;
end;
for i:= to n do
begin
readln(s);
for j:= to m do
begin
b[i,j]:=ord(s[j])-;
sum:=sum+b[i,j];
end;
end;
for i:= to n do
begin
readln(s);
for j:= to m do
c[i,j]:=ord(s[j])-;
end;
if sum<>tot then
begin
writeln(-);
halt;
end
else ch:=sum;
sum:=n*m;
for i:= to n do
begin
for j:= to m do
begin
x:=(i-)*m+j;
if a[i,j]= then
begin
add(x+sum,x,c[i,j] shr ,);
add(x,x+sum,,);
add(x,x+*sum,(c[i,j]+) shr ,);
add(x+*sum,x,,);
add(,x,,);
add(x,,,);
if b[i,j]= then //细节
begin
add(x,t,,);
add(t,x,,);
end;
end
else if b[i,j]= then
begin
add(x+sum,x,(c[i,j]+) shr ,);
add(x,x+sum,,);
add(x,x+*sum,c[i,j] shr ,);
add(x+*sum,x,,);
add(x,t,,);
add(t,x,,);
end
else if (a[i,j]+b[i,j]=) then
begin
add(x+sum,x,c[i,j] shr ,);
add(x,x+sum,,);
add(x,x+*sum,c[i,j] shr ,);
add(x+*sum,x,,);
end;
end;
end; for i:= to n do
for j:= to m do
begin
po:=(i-)*m+j;
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if (x<=n) and (y<=m) and (x>) and (y>) then
begin
tot:=(x-)*m+y;
add(po+*sum,tot+sum,inf,);
add(tot+sum,po+*sum,,-);
end;
end;
end;
mincost;
if ch<> then writeln(-) else writeln(ans);
end.