#include<stdio.h>#include<string.h>#include<algorithm>#define HASH 41941 #define SIZE 100010#define MAXN 15struct HashMap{ int head[HASH], size, next[SIZE], st[SIZE], f[SIZE]; void init() { memset(head, -1, sizeof(head)), size = 0; } void push(int _st, int _f) { int i, h = _st % HASH; for(i = head[h]; i != -1; i = next[i]) if(st[i] == _st) break; if(i == -1) { st[size] = _st, f[size] = _f; next[size] = head[h], head[h] = size ++; } else f[i] = std::min(f[i], _f); }}hm[2];int N, M, g[MAXN][MAXN], h[MAXN], pre[MAXN];inline int enpre(int *pre, int m){ int i, st = 0, cnt = 2; memset(h, -1, sizeof(h)), h[0] = 0, h[1] = 1, h[2] = 2; for(i = 0; i <= m; i ++) { if(h[pre[i]] == -1) h[pre[i]] = ++ cnt; st = st << 3 | h[pre[i]]; } return st;}inline void depre(int *pre, int m, int st){ for(int i = m; i >= 0; i --) pre[i] = st & 7, st >>= 3; }void init(){ int i, j; memset(g, 0, sizeof(g)); for(i = 1; i <= N; i ++) for(j = 1; j <= M; j ++) { scanf("%d", &g[i][j]); if(g[i][j] == 0) g[i][j] = 1; else if(g[i][j] == 1) g[i][j] = 0; }}inline void trans(int x, int y){ for(int i = 0; i <= M; i ++) if(pre[i] == x) pre[i] = y; }void dpblock(int i, int j, int cur){ int k; for(k = 0; k < hm[cur].size; k ++) hm[cur ^ 1].push(hm[cur].st[k] >> 3 * (j == M), hm[cur].f[k]);}void dpblank(int i, int j, int cur){ int k; for(k = 0; k < hm[cur].size; k ++) { depre(pre, M, hm[cur].st[k]); if(pre[j] && pre[j - 1]) { if(pre[j] <= 2 && pre[j - 1] <= 2 && pre[j] != pre[j - 1]) continue; if(pre[j] != pre[j - 1]) trans(std::max(pre[j], pre[j - 1]), std::min(pre[j], pre[j - 1])); pre[j] = pre[j - 1] = 0; hm[cur ^ 1].push(enpre(pre, M - (j == M)), hm[cur].f[k] + 1); } else if(pre[j]) { if(g[i][j + 1]) hm[cur ^ 1].push(hm[cur].st[k], hm[cur].f[k] + 1); if(g[i + 1][j]) { pre[j - 1] = pre[j], pre[j] = 0; hm[cur ^ 1].push(enpre(pre, M - (j == M)), hm[cur].f[k] + 1); } } else if(pre[j - 1]) { if(g[i + 1][j]) hm[cur ^ 1].push(hm[cur].st[k] >> 3 * (j == M), hm[cur].f[k] + 1); if(g[i][j + 1]) { pre[j] = pre[j - 1], pre[j - 1] = 0; hm[cur ^ 1].push(enpre(pre, M), hm[cur].f[k] + 1); } } else { hm[cur ^ 1].push(hm[cur].st[k] >> 3 * (j == M), hm[cur].f[k]); if(g[i][j + 1] && g[i + 1][j]) { pre[j] = pre[j - 1] = M + 2; hm[cur ^ 1].push(enpre(pre, M), hm[cur].f[k] + 1); } } } }void dp(int i, int j, int cur){ int k; for(k = 0; k < hm[cur].size; k ++) { depre(pre, M, hm[cur].st[k]); if(pre[j] && pre[j - 1]) continue; else if(pre[j]) { if(pre[j] <= 2 && pre[j] != g[i][j] - 1) continue; if(pre[j] > 2) trans(pre[j], g[i][j] - 1); pre[j] = 0; hm[cur ^ 1].push(enpre(pre, M - (j == M)), hm[cur].f[k] + 1); } else if(pre[j - 1]) { if(pre[j - 1] <= 2 && pre[j - 1] != g[i][j] - 1) continue; if(pre[j - 1] > 2) trans(pre[j - 1], g[i][j] - 1); pre[j - 1] = 0; hm[cur ^ 1].push(enpre(pre, M - (j == M)), hm[cur].f[k] + 1); } else { if(g[i][j + 1]) { pre[j] = g[i][j] - 1; hm[cur ^ 1].push(enpre(pre, M), hm[cur].f[k] + 1); pre[j] = 0; } if(g[i + 1][j]) { pre[j - 1] = g[i][j] - 1; hm[cur ^ 1].push(enpre(pre, M - (j == M)), hm[cur].f[k] + 1); } } }}void solve(){ int i, j, cur = 0; hm[0].init(), hm[0].push(0, 0); for(i = 1; i <= N; i ++) for(j = 1; j <= M; j ++) { hm[cur ^ 1].init(); if(g[i][j] == 0) dpblock(i, j, cur); else if(g[i][j] == 1) dpblank(i, j, cur); else dp(i, j, cur); cur ^= 1; } if(hm[cur].size == 0) printf("0n"); else printf("%dn", hm[cur].f[0] - 2);}int main(){ while(scanf("%d%d", &N, &M), N) { init(); solve(); } return 0; }
