记录编号	88099	评测结果	AAAAAAAAAA
题目名称	[UVa 1408] 飞行控制	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	4.871 s
提交时间	2014-02-16 11:54:38	内存使用	103.71 MiB

#include<iostream>
#include<cstdio>
#include<deque>
#include<cstring>
#include<iomanip>
using namespace std;
const int SIZEN=51,SIZEM=9,SIZES=59049,INF=500;
int board[SIZEN+1][SIZEM+1];
int N,M;
int f[SIZEN][SIZEM][SIZES];
class STATE{
public:
	//0无,1:向当前格子递增,2:向当前格子递减
	int up[SIZEM];
	int left;
	void print(void){
		cout<<"up:";
		for(int i=0;i<M;i++) cout<<up[i]<<" ";
		cout<<endl<<"left:"<<left<<endl;
	}
	void clear(void){
		memset(up,0,sizeof(up));
		left=0;
	}
	int mdl(void){
		int s=left;
		for(int i=0;i<M;i++) s=s*3+up[i];
		return s;
	}
};
int cmp(int a,int b){
	if(b>a) return 1;
	if(b<a) return 2;
	return 0;
}
int DP(int x,int y,STATE &S){
	if(y==M){
		x++,y=0;
		S.left=0;
	}
	if(x==N){
		return 0;
	}
	int &ans=f[x][y][S.mdl()],temp;
	if(ans!=-1) return ans;
	ans=INF;
	STATE T;
	if(board[x][y]<=0){
		T=S;T.left=0;T.up[y]=0;
		return ans=DP(x,y+1,T);
	}
	if(S.left&&S.left==cmp(board[x][y-1],board[x][y])){//横向可顺延
		T=S;T.left=S.left;T.up[y]=0;
		ans=min(ans,DP(x,y+1,T));
	}
	else{//不可顺延
		T=S;T.left=cmp(board[x][y],board[x][y+1]);T.up[y]=0;
		ans=min(ans,DP(x,y+1,T)+1);
	}
	if(S.up[y]&&S.up[y]==cmp(board[x-1][y],board[x][y])){//纵向可顺延
		T=S;T.left=0;T.up[y]=S.up[y];
		ans=min(ans,DP(x,y+1,T));
	}
	else{//不可顺延
		T=S;T.left=0;T.up[y]=cmp(board[x][y],board[x+1][y]);
		ans=min(ans,DP(x,y+1,T)+1);
	}
	return ans;
}
int kase=0;
void work(void){
	memset(f,-1,sizeof(f));
	STATE S;
	S.clear();
	printf("Case %d: %d\n",++kase,DP(0,0,S));
}
bool read(void){
	scanf("%d%d",&N,&M);
	if(!N&&!M) return false;
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++) scanf("%d",&board[i][j]);
	}
	for(int i=0;i<N;i++) board[i][M]=board[i][M-1];
	for(int i=0;i<M;i++) board[N][i]=board[N-1][i];
	return true;
}
int main(){
	freopen("flightcontrol.in","r",stdin);
	freopen("flightcontrol.out","w",stdout);
	while(read()) work();
	return 0;
}