Description
有一个n行m列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。
Input
第一行包含两个整数n，m（1<=n,
m<=20）。以下n行为初始状态，每行为一个包含m个字符的01串，其中0表示黑色棋子，1表示白色棋子。以下n行为目标状态，格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串，表示每个格子参与交换的次数上限。
m<=20）。以下n行为初始状态，每行为一个包含m个字符的01串，其中0表示黑色棋子，1表示白色棋子。以下n行为目标状态，格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串，表示每个格子参与交换的次数上限。
Output
输出仅一行，为最小交换总次数。如果无解，输出-1。
Sample Input
3 3
110
000
001
000
110
100
222
222
222
110
000
001
000
110
100
222
222
222
Sample Output
4
网络流
明显格子等价于可以互相穿过，棋子是一样的
原本就在位置上的棋子我们没必要移
program bzoj2668;
const
zl:array [1..8,1..2] of longint=((1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1));
var
tot,u,v,x,y,count,ans,n,m,i,j,k:longint;
lim:array [0..21,0..21] of longint;
a,b:array [0..21,0..21] of char;
last,dis,root:array [0..801] of longint;
dl,point,next,cost,flow:array [0..100001] of longint;
ch:char;
function anti (now:longint):longint;inline;
begin
if now and 1 = 1 then exit(now+1)
else exit(now-1);
end;
procedure connect (u,v,f,c:longint);inline;
begin
inc(tot);
point[tot]:=v;
flow[tot]:=f;
cost[tot]:=c;
next[tot]:=root[u];
root[u]:=tot;
end;
procedure mcmf;
begin
repeat
fillchar(dis,sizeof(dis),63);
tot:=0;
dl[0]:=0;
dis[0]:=0;
i:=0;
while i<=tot do
begin
k:=root[dl[i]];
while k<>0 do
begin
if (flow[k]>0)and(dis[point[k]]>dis[dl[i]]+cost[k]) then
begin
last[point[k]]:=k;
dis[point[k]]:=dis[dl[i]]+cost[k];
inc(tot);
dl[tot]:=point[k];
end;
k:=next[k];
end;
inc(i);
end;
if dis[801]>1000000 then break;
dec(count);
ans:=ans+dis[801];
i:=801;
while i<>0 do
begin
dec(flow[last[i]]);
inc(flow[anti(last[i])]);
i:=point[anti(last[i])];
end;
until false;
end;
begin
readln(n,m);
count:=0;
for i:=1 to n do
begin
for j:=1 to m do
begin
read(a[i,j]);
if a[i,j]='1' then inc(count);
end;
readln;
end;
k:=0;
for i:=1 to n do
begin
for j:=1 to m do
begin
read(b[i,j]);
if b[i,j]='1' then inc(k);
end;
readln;
end;
if count<>k then
begin
writeln(-1);
exit;
end;
for i:=1 to n do
begin
for j:=1 to m do
begin
read(ch);
lim[i,j]:=ord(ch)-48;
end;
readln;
end;
for i:=1 to n do
for j:=1 to m do
if (a[i,j]='1')and(b[i,j]='1') then
begin
dec(count);
k:=i*m-m+j;
connect(k*2-1,k*2,lim[i,j] div 2,0);
connect(k*2,k*2-1,0,0);
end
else
if (a[i,j]='1')or(b[i,j]='1') then
begin
k:=i*m-m+j;
if lim[i,j]=0 then
begin
writeln(-1);
exit;
end;
connect(k*2-1,k*2,(lim[i,j]-1) div 2 + 1,0);
connect(k*2,k*2-1,0,0);
if a[i,j]='1' then
begin
connect(0,k*2-1,1,0);
connect(k*2-1,0,0,0);
end;
if b[i,j]='1' then
begin
connect(k*2,801,1,0);
connect(801,k*2,0,0);
end;
end
else
begin
k:=i*m-m+j;
connect(k*2-1,k*2,lim[i,j] div 2,0);
connect(k*2,k*2-1,0,0);
end;
for i:=1 to n do
for j:=1 to m do
for k:=1 to 8 do
begin
x:=i+zl[k,1];
y:=j+zl[k,2];
if (x<1)or(x>n)or(y<1)or(y>m) then continue;
u:=i*m-m+j;
v:=x*m-m+y;
connect(u*2,v*2-1,maxlongint div 10,1);
connect(v*2-1,u*2,0,-1);
end;
mcmf;
if count<>0 then
begin
writeln(-1);
exit;
end;
writeln(ans);
end.