1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inf 0x3F3F3F3F
using namespace std;
struct Node
{
int to,next,v,cost;
}e[100005];
int S,T,P,a[25][25],b[25][25],num1[25][25],num2[25][25],cnt=1;
int h[10005],d[10005],pre[10005],flow,cost;
bool vis[10005];
inline void Addedge(int x,int y,int v,int cost=0)
{
e[++cnt]=(Node){y,h[x],v,cost};h[x]=cnt;
e[++cnt]=(Node){x,h[y],0,-cost};h[y]=cnt;
return;
}
inline bool SPFA()
{
int i,x,y;
queue<int>q;q.push(S);
memset(d,0x3F,sizeof(d));d[S]=0;
memset(vis,0,sizeof(vis));
memset(pre,0,sizeof(pre));
while(!q.empty())
{
x=q.front();q.pop();
vis[x]=false;
for(i=h[x];i;i=e[i].next)
{
y=e[i].to;
if(e[i].v&&d[y]>d[x]+e[i].cost)
{
d[y]=d[x]+e[i].cost;
pre[y]=i;
if(!vis[y]){vis[y]=true;q.push(y);}
}
}
}
if(d[T]<0x3F3F3F3F)return true;
return false;
}
inline void Adjust()
{
int i,j=T,delta=0x3F3F3F3F;
while(pre[j])
{
i=pre[j];
if(e[i].v<delta)delta=e[i].v;
j=e[i^1].to;
}
cost+=delta*d[T];
flow+=delta;
j=T;
while(pre[j])
{
i=pre[j];
e[i].v-=delta;
e[i^1].v+=delta;
j=e[i^1].to;
}
return;
}
const int dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
int main(void)
{
int i,j,k,x,newx,newy,n,m,ch,sum=0,id=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
while(ch=getchar())if(ch>='0'&&ch<='9')break;
a[i][j]=ch-'0';sum+=a[i][j];
}
}
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
while(ch=getchar())if(ch>='0'&&ch<='9')break;
b[i][j]=ch-'0';sum-=b[i][j];
}
}
if(sum){printf("-1\n");return 0;}
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)num1[i][j]=++id;
}
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)num2[i][j]=++id;
}
S=2*n*m+1;T=P=2*n*m+2;
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
if(a[i][j]&&!b[i][j])Addedge(S,num1[i][j],1),++sum;
if(!a[i][j]&&b[i][j])Addedge(num2[i][j],T,1);
}
}
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
while(ch=getchar())if(ch>='0'&&ch<='9')break;
x=ch-'0';
Addedge(num1[i][j],num2[i][j],x>>1);
if((a[i][j]!=b[i][j])&&(x&1))Addedge(num1[i][j],num2[i][j],1);
for(k=0;k<8;++k)
{
newx=i+dx[k];newy=j+dy[k];
if(newx<1||newx>n||newy<1||newy>m)continue;
Addedge(num2[i][j],num1[newx][newy],inf,1);
}
}
}
while(SPFA())Adjust();
if(flow!=sum){printf("-1\n");return 0;}
printf("%d\n",cost);
return 0;
}
|