Description：

一个 $n$ 行 $m$ 列的黑白棋盘，每次可以交换两个八相邻格子中的棋子，最终达到目标状态。要求第 $i$ 行第 $j$ 列的格子只能参与 $m_{i,j}$ 次交换，求最小交换次数。

$1\leqslant n,m\leqslant 20$

Solution：

首先一个显然的想法是把棋子从开始移到最后的路径看成一个流，边权为一，求最小费用最大流，然后仔细想一想感觉应该可以拆点，但是限制很不好做，看了题解之后发现可以拆三个点，然后用三个点之间的限制来做，即如果这个格子开始是黑色，那么从源点向中间的点连边，如果结束是黑色，那么从中间的点向汇点连边，然后把一个当入点，一个当出点，然后会发现进入和出去的流量是可以计算出的，一个是 $\frac{w[i][j]}2$ ，一个是 $\lceil\frac{w[i][j]}2\rceil$ ，这样连边就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int getc()

{

	char c = getchar();

	while(!isdigit(c))c = getchar();

	return c - '0';

}

int n,m;

#define MAXN 22

int a[MAXN][MAXN],b[MAXN][MAXN],w[MAXN][MAXN];

struct edge

{

	int to,nxt,f,w;

}e[MAXN * MAXN * 24];

int edgenum = 0;

int lin[MAXN * MAXN * 3];

void add(int a,int b,int f,int w)

{

	e[edgenum] = (edge){b,lin[a],f, w};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0,-w};lin[b] = edgenum++;

	return;

}

int mx[8] = {0,0,1,-1,1,1,-1,-1};

int my[8] = {1,-1,0,0,-1,1,1,-1};

int to(int i,int j,int k){return ((i - 1) * m + j - 1) * 3 + k;}

int d[MAXN * MAXN * 3],pre[MAXN * MAXN * 3],rate[MAXN * MAXN * 3];

bool v[MAXN * MAXN * 3];

int s,t;

#define INF 0x3f3f3f3f

int cnta = 0,cntb = 0;

int sum = 0;

bool SPFA()

{

	memset(d,0x3f,sizeof(d));d[s] = 0;

	queue<int> q;q.push(s);

	rate[s] = INF;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].w && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].w;

				pre[e[i].to] = i;

				rate[e[i].to] = min(rate[k],e[i].f);

				if(!v[e[i].to])

				{

					q.push(e[i].to);

					v[e[i].to] = true;

				}

			}

		}

	}

	return (d[t] != INF);

}

int flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	sum += rate[t];

	return rate[t] * d[t];

}

int EK()

{

	int ans = 0;

	while(SPFA())ans += flow();

	if(sum != cnta)return -1;

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			a[i][j] = getc();

			if(a[i][j] == 1)++cnta;

		}

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			b[i][j] = getc();

			if(b[i][j] == 1)++cntb;

		}

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			w[i][j] = getc();

		}

	}

	if(cnta != cntb)

	{

		puts("-1");

		return 0;

	}

	s = n * m * 3 + 1;t = s + 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if(a[i][j] == 1 && b[i][j] == 0)

			{

				add(to(i,j,1),to(i,j,2),w[i][j] / 2,0);

				add(s,to(i,j,2),1,0);

				add(to(i,j,2),to(i,j,3),(w[i][j] + 1) / 2,0);

			}

			else if(a[i][j] == 0 && b[i][j] == 1)

			{

				add(to(i,j,1),to(i,j,2),(w[i][j] + 1) / 2,0);

				add(to(i,j,2),t,1,0);

				add(to(i,j,2),to(i,j,3),w[i][j] / 2,0);

			}

			else

			{

				add(to(i,j,1),to(i,j,2),w[i][j] / 2,0);

				add(to(i,j,2),to(i,j,3),w[i][j] / 2,0);

				if(a[i][j] == 1 && b[i][j] == 1)

				{

					add(s,to(i,j,2),1,0);

					add(to(i,j,2),t,1,0);

				}

			}

			for(int k = 0;k < 8;++k)

			{

				if(i + mx[k] >= 1 && i + mx[k] <= n && j + my[k] >= 1 && j + my[k] <= m)

				{

					add(to(i,j,3),to(i + mx[k],j + my[k],1),INF,1);

				}

			}

		}

	}

	cout << EK() << endl;

	return 0;

}