Descirption:

Solution:

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

int n,m;

#define MAXN 13

int map[MAXN][MAXN];

#define HASH 30007

#define STATE 3000000

struct hash

{

	int head[HASH],next[STATE],siz;

	ll data[STATE],f[STATE];

	void init(){memset(head,0,sizeof(head));siz = 0;return;}

	void add(ll state,ll ans)

	{

		int hash = state % HASH;

		for(int i = head[hash];i != 0;i = next[i])if(data[i] == state){f[i] = min(ans,f[i]);return;}

		++siz;data[siz] = state;f[siz] = ans;next[siz] = head[hash];head[hash] = siz;

		return;

	}

}h[2];

int code[MAXN],code_[MAXN];

void decode(int *code,int m,ll state)

{

	for(int i = m;i >= 0;--i)

	{

		code[i] = state & 3;

		state = state >> 2;

	}

	return;

}

ll encode(int *code,int m)

{

	ll state = 0;

	for(int i = 0;i <= m;++i)

	{

		state = state << 2;

		state |= code[i];

	}

	return state;

}

void shift(int *code,int *code_,int m)

{

	for(int i = m;i > 0;--i)code_[i] = code[i - 1];

	code_[0] = 0;

	return;

}

void copy(int *code,int *code_,int m)

{

	for(int i = m;i >= 0;--i)code_[i] = code[i];

	return;

}

void dp(int i,int j,int cur)

{

	int left,up;

	for(int k = 1;k <= h[cur].siz;++k)

	{

		decode(code,m,h[cur].data[k]);//cout << ":   ";for(int l = 0;l <= m;++l)cout << code[l] << " ";cout << "  " << h[cur].f[k] << endl;

		left = code[j - 1];up = code[j];

		if(map[i][j] == 1)

		{//cout << 0 << endl;

			if(left == 0 && up == 0)

			{//cout << "  " << 0 << endl;

				if(map[i + 1][j] != 0 && map[i][j + 1] != 0)

				{

					if((map[i + 1][j] == 1 || map[i + 1][j] == 2) && (map[i][j + 1] == 1 || map[i][j + 1] == 2))

					{

						code[j - 1] = 2;code[j] = 2;

						if(j == m)shift(code,code_,m);else copy(code,code_,m);

						h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + 1);

					}

					if((map[i + 1][j] == 1 || map[i + 1][j] == 3) && (map[i][j + 1] == 1 || map[i][j + 1] == 3))

					{

						code[j - 1] = 3;code[j] = 3;

						if(j == m)shift(code,code_,m);else copy(code,code_,m);

						h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + 1);

					}

				}

				code[j - 1] = 0;code[j] = 0;

				if(j == m)shift(code,code_,m);else copy(code,code_,m);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

			if((left != 0 && up == 0) || (left == 0 && up != 0))

			{//cout << "  " << 1 << endl;

				int t;

				if(left)t = left;

				else t = up;

				if(map[i + 1][j] == 1 || map[i + 1][j] == t)

				{

					code[j - 1] = t;code[j] = 0;

					if(j == m)shift(code,code_,m);else copy(code,code_,m);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + 1);

				}

				if(map[i][j + 1] == 1 || map[i][j + 1] == t)

				{

					code[j - 1] = 0;code[j] = t;

					if(j == m)shift(code,code_,m);else copy(code,code_,m);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + 1);

				}

			}

			if(left != 0 && up != 0)

			{

				if(left == up)

				{//cout << "  " << 3 << endl;

					code[j - 1] = code[j] = 0;

					if(j == m)shift(code,code_,m);else copy(code,code_,m);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + 1);

				}

			}

		}

		if(map[i][j] == 2 || map[i][j] == 3)

		{//cout << 2 << endl;

			int t = map[i][j];

			if(left == 0 && up == 0)

			{

				if(map[i + 1][j] == 1 || map[i + 1][j] == t)

				{

					code[j - 1] = t;code[j] = 0;

					if(j == m)shift(code,code_,m);else copy(code,code_,m);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + 1);

				}

				if(map[i][j + 1] == 1 || map[i][j + 1] == t)

				{

					code[j - 1] = 0;code[j] = t;

					if(j == m)shift(code,code_,m);else copy(code,code_,m);

					h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + 1);

				}

			}

			if((left == 0 && up == t) || (left == t && up == 0))

			{

				code[j - 1] = 0;code[j] = 0;

				if(j == m)shift(code,code_,m);else copy(code,code_,m);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + 1);

			}

		}

		if(map[i][j] == 0)

		{//cout << 3 << endl;

			if(left == 0 && up == 0)

			{

				if(j == m)shift(code,code_,m);else copy(code,code_,m);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

			}

		}

	}

	return;

}

void solve()

{

	int cur = 0;

	h[cur].init();

	h[cur].add(0,0);

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

	{

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

		{//cout << i << " " << j << endl;

			h[cur ^ 1].init();

			dp(i,j,cur);

			cur ^= 1;

		}

	}

	ll res = 0;

	for(int i = h[cur].head[0];i != 0;i = h[cur].next[i])

	{

		if(h[cur].data[i] == 0)

		{

			res = h[cur].f[i];

		}

	}

	if(res == 0)puts("0");

	else cout << res - 2 << endl;

	return;

}

void work()

{

	memset(map,0,sizeof(map));

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

	{

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

		{

			scanf("%d",&map[i][j]);

			if(map[i][j] == 1 || map[i][j] == 0)map[i][j] ^= 1;

		}

	}

	solve();

	return;

}

int main()

{

	while(scanf("%d%d",&n,&m) && n != 0 && m != 0)work();

	return 0;

}