代码果然强悍，没看解题报告，读了一天，终于把你的思路读通了。
好像有一点没考虑：换行的时候，如果left不是0会怎么样，会不会影响到最终的结果。
我没有ctrl+a+ctrl+c+ctrl+v+alt+s，而是把代码翻译成了gcc版，供大家参考

#include <stdio.h>
#include <stdlib.h>

#define MAX_N		9
#define MAX_M		9
#define MAX_STATE	1048576 /* 4^(MAX_M + 1) */
#define HI(x)		(x << (2 * m))

int n, m;
int board[MAX_N][MAX_M];

int queue[2][MAX_STATE];
int head[2], tail[2];
int v[MAX_STATE];
int curr_flag;
int len[2][MAX_STATE];
int *qc, *qn, *headc, *headn, *tailc, *tailn, *lenc, *lenn;
int step;

void init_queue() {
	qc = queue[step];
	headc = &head[step];
	tailc = &tail[step];
	lenc = len[step];
	step ^= 1;
	qn = queue[step];
	headn = &head[step];
	tailn = &tail[step];
	lenn = len[step];
	*headn = *tailn = 0;
	++curr_flag;
}

void add_state(int state, int l) {
	if(v[state] == curr_flag) {
		if(l < lenn[state])
			lenn[state] = l;
		return;
	}
	v[state] = curr_flag;
	lenn[state] = l;
	qn[*tailn] = state;
	*tailn += 1;
}

void dp() {
	int i, j;
	int left, last; /* expectation from left element & last row */
	int cs, ns, cl;
	head[step] = tail[step] = 0;
	queue[step][tail[step]] = 0;
	len[step][0] = 0;
	++tail[step];
	for(i = 0; i < n; ++i) {
		for(j = 0; j < m; ++j) {
			init_queue();
			while(*headc != *tailc) {
				cs = qc[*headc];
				*headc += 1;
				cl = lenc[cs];
				left = cs & 3;
				ns = cs >> 2;
				last = ns & 3;
				if(j == 0 && left != 0)
					continue;
				switch(board[i][j]) {
				case 0:
					if(left == 0 && last == 0) {
						add_state(ns, cl);
						add_state(ns | HI(2) | 2, cl + 1);
						add_state(ns | HI(3) | 3, cl + 1);
					}
					else if(left != 0 && last == 0) {
						add_state(ns | left, cl + 1);
						add_state(ns | HI(left), cl + 1);
					}
					else if(left == 0 && last != 0) {
						add_state(ns, cl + 1); /* ns & ~last | last */
						add_state((ns & ~last) | HI(last), cl + 1);
					}
					else if(left == last)
						add_state(ns & ~last, cl + 1);
					break;
				case 1:
					if(left == 0 && last == 0)
						add_state(ns, cl);
					break;
				case 2:
				case 3:
					if(left == 0 && last == 0) {
						add_state(ns | board[i][j], cl + 1);
						add_state(ns | HI(board[i][j]), cl + 1);
					}
					else if(left == board[i][j] && last == 0)
						add_state(ns, cl + 1);
					else if(left == 0 && last == board[i][j])
						add_state(ns & ~last, cl + 1);
					break;
				} /* switch */
			} /* while */
		} /* inner for */
	} /* outer for */
	if(v[0] == curr_flag)
		printf("%d\n", lenn[0] - 2);
	else
		fputs("0\n", stdout);
}

int main(int argc, char *argv[]) {
	int i, j;
	while(scanf("%d %d", &n, &m), !(n == 0 && m == 0)) {
		for(i = 0; i < n; ++i) {
			for(j = 0; j < m; ++j)
				scanf("%d", &board[i][j]);
		}
		dp();
	}
	exit(0);
}