Description：

一个棋盘，每个位置可能是 $+,\urcorner,\lrcorner,\llcorner,\ulcorner,\top,\vdash,\bot,|,-$ 之一，每次操作可以转 $90^\circ$ ，直线型不能转动，问最少操作几次使得水管闭合。

$1\leqslant n\times m\leqslant 2000$

Solution：

先把每个点拆成四个点，然后把棋盘黑白染色，从源点向黑的当前有的断点连，从白点当前有的断点向汇点连，然后相邻的点之间连，然后考虑转动的情况，分情况讨论：

$1$ 、 $\urcorner\ $ 型：把有的向对面没有的费用为 $1$ 连边，这样如果只转动一次的话会有一个费用，转动两次的话都经过费用为 $2$ 。

$2$ 、 $\circ-$ 型：向两边连费用为 $1$ 的边，向后边连费用为 $2$ 的边。

$3$ 、 $\top$ 型：这个我们可以看成是有一个断点没有经过转而经过了另一个，那么我们就可以分别对于每个当前已经有的断点向当前没有的点连对应权值的边即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 2010

#define to(i,j,k) (((i - 1) * m + j - 1) * 4 + k)

struct edge

{

	int to,nxt,f,w;

}e[MAXN * 6 * 2];

int edgenum = 0;

int lin[MAXN * 4];

inline 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 d[MAXN * 4],pre[MAXN * 4],rate[MAXN * 4];

bool v[MAXN * 4];

int s,t;

#define INF 0x3f3f3f3f

#define R register

inline bool SPFA()

{

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

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

	rate[s] = INF;

	while(!q.empty())

	{

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

		v[k] = false;

		for(R 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])

				{

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

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

				}

			}

		}

	}

	return (d[t] != INF);

}

int ans = 0,sum = 0,tot = 0;

inline void flow()

{

	R int x = rate[t];

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

	{

		e[pre[i]].f -= x;

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

	}

	ans += x * d[t];

	tot += x;

	return;

}

inline void EK()

{

	while(SPFA())flow();

	return;

}

inline void set(int x,int y,int v)

{

	if(v == 0)return; 

	R bool flag = bool((x + y) % 2);

	v = v << 1;

	R int cnt = 0;

	for(R int i = 1;i <= 4;++i)

	{

		if(v & (1 << i))

		{

			if(flag)add(s,to(x,y,i),1,0);

			else add(to(x,y,i),t,1,0);

			++cnt;

		}

	}

	sum += cnt;

	if(cnt == 1)

	{

		R int p;

		for(R int i = 1;i <= 4;++i)

		{

			if(v & (1 << i))

			{

				p = i;

				break;

			}

		}

		for(R int i = 1;i <= 4;++i)

		{

			if(i == p)continue;

			if((i ^ p) & 1)

			{

				if(flag)add(to(x,y,p),to(x,y,i),1,1);

				else add(to(x,y,i),to(x,y,p),1,1);

			}

			else 

			{

				if(flag)add(to(x,y,p),to(x,y,i),1,2);

				else add(to(x,y,i),to(x,y,p),1,2);

			}

		}

	}

	if(cnt == 2)

	{

		if(((v >> 1) & 1) != ((v >> 3) & 1))

		{

			for(R int i = 1;i <= 4;++i)

			{

				if(v & (1 << i))continue;

				if(flag)add(to(x,y,(i + 1) % 4 + 1),to(x,y,i),1,1);

				else add(to(x,y,i),to(x,y,(i + 1) % 4 + 1),1,1);

			}

		}

	}

	if(cnt == 3)

	{

		for(R int i = 1;i <= 4;++i)

		{

			if(v & (1 << i))continue;

			if(flag)

			{

				add(to(x,y,(i + 1) % 4 + 1),to(x,y,i),1,2);

				add(to(x,y,i % 4 + 1),to(x,y,i),1,1);

				add(to(x,y,(i + 2) % 4 + 1),to(x,y,i),1,1);

			}

			else

			{

				add(to(x,y,i),to(x,y,(i + 1) % 4 + 1),1,2);

				add(to(x,y,i),to(x,y,i % 4 + 1),1,1);

				add(to(x,y,i),to(x,y,(i + 2) % 4 + 1),1,1);

			}

		}

	}

	if(flag)

	{

		if(x != 1)add(to(x,y,1),to(x - 1,y,3),1,0);

		if(y != m)add(to(x,y,2),to(x,y + 1,4),1,0);

		if(x != n)add(to(x,y,3),to(x + 1,y,1),1,0);

		if(y != 1)add(to(x,y,4),to(x,y - 1,2),1,0);

	}

	return;

}

int main()

{

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

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

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

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

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

			set(i,j,rd());

	EK();

	if(sum != tot * 2)puts("-1");

	else cout << ans << endl;

	return 0;

}