记录编号	87634	评测结果	AAAAAAAAAA
题目名称	[UVa 1214] 连线	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	10.740 s
提交时间	2014-02-06 15:08:28	内存使用	22.84 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iomanip>
using namespace std;
typedef long long ll;
const int INF=0x7fffffff/2;
const int SIZEN=10;
int N,M;
int grid[SIZEN][SIZEN]={0};
class STATE{
public:
	int x,y;//当前应该在这一格放线
	int up[SIZEN];//上方的编号
	//这是上方的M个插头
	int left;//左侧的编号
	void clear(void){
		x=y=left=0;
		memset(up,0,sizeof(up));
	}
	int mdl(void){
		int ans=left;
		for(int i=1;i<=M;i++) ans=ans*3+up[i];
		return ans;
	}
	bool placeblock(int U,int D,int L,int R){//若这个放法不行就返回false,否则把S改成这个放法
		if(U&&x==1) return false;//不能通向边界
		if(L&&y==1) return false;
		if(D&&x==N) return false;
		if(R&&y==M) return false;
		if(L!=left) return false;//左不匹配
		if(U!=up[y]) return false;//上不匹配
		if(left>0&&up[y]>0&&left!=up[y]) return false;//左和上不匹配
		left=R;
		up[y]=D;
		y++;
		return true;
	}
};
int f[10][10][59050]={0};
int DP(STATE &S){
	/*
	一个合法方案只需满足五个条件:
	1:空格有0或2个插头
	2:2/3格有1个插头
	3:相邻两格插头必须对应(有对有,无对无)
	4:2和3插头不能相连
	5:不能有通向边界的插头
	*/
	if(S.y==M+1){
		S.left=0;//这个插头是无效的,其他插头没有变
		S.y=1,S.x++;
	}
	if(S.x==N+1) return 0;//到这里了一定合法
	int &ans=f[S.x][S.y][S.mdl()];
	if(ans>=0) return ans;
	ans=INF;
	STATE T;
	if(grid[S.x][S.y]<=1){//空格或障碍格
		T=S;if(T.placeblock(0,0,0,0)) ans=min(ans,DP(T));//可以不放
		if(grid[S.x][S.y]==0){//空格
			//如果放,就是连了两条边
			for(int t=1;t<=2;t++){//当前放一条t线
				//这条线的长度是一格,考虑到要是整数所以将半格认为是1
				T=S;if(T.placeblock(t,t,0,0)) ans=min(ans,DP(T)+2);
				T=S;if(T.placeblock(t,0,t,0)) ans=min(ans,DP(T)+2);
				T=S;if(T.placeblock(t,0,0,t)) ans=min(ans,DP(T)+2);
				T=S;if(T.placeblock(0,t,t,0)) ans=min(ans,DP(T)+2);
				T=S;if(T.placeblock(0,t,0,t)) ans=min(ans,DP(T)+2);
				T=S;if(T.placeblock(0,0,t,t)) ans=min(ans,DP(T)+2);
			}
		}
	}
	else{
		int t=grid[S.x][S.y]-1;//格子有2和3,但线对应的是1和2
		//这条线的长度是半格
		T=S;if(T.placeblock(t,0,0,0)) ans=min(ans,DP(T)+1);
		T=S;if(T.placeblock(0,t,0,0)) ans=min(ans,DP(T)+1);
		T=S;if(T.placeblock(0,0,t,0)) ans=min(ans,DP(T)+1);
		T=S;if(T.placeblock(0,0,0,t)) ans=min(ans,DP(T)+1);
	}
	return ans;
}
void work(void){
	memset(f,-1,sizeof(f));
	STATE S;
	S.clear();//这时所有的插头都是空的
	S.x=S.y=1;
	int ans=DP(S);
	if(ans==INF) printf("0\n");
	else printf("%d\n",ans/2);
}
bool read(void){
	scanf("%d%d",&N,&M);
	if(!N&&!M) return false;
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) scanf("%d",&grid[i][j]);
	return true;
}
int main(){
	freopen("manhattanwiring.in","r",stdin);
	freopen("manhattanwiring.out","w",stdout);
	while(read()) work();
	return 0;
}