zoj 3213 Beautiful Meadow

zoj 3213 Beautiful Meadow

#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>using namespace std;const int MAXD=15;const int HASH=10007;const int STATE=1000010;int N,M;int maze[MAXD][MAXD];int pre[MAXD];int ch[MAXD];int num;int ans;struct HASHMAP{ int head[HASH],next[STATE],size; int state[STATE],dp[STATE]; void init() { size=0; memset(head,-1,sizeof(head)); } void push(int st,int ans) { int i,h=st%HASH; for(i=head[h];i!=-1;i=next[i]) if(state[i]==st) { if(dp[i]<ans)dp[i]=ans; return; } state[size]=st; dp[size]=ans; next[size]=head[h]; head[h]=size++; }}hm[2];void depre(int *pre,int m,int st){ num=st&7; st>>=3; for(int i=m;i>=0;i--) { pre[i]=st&7; st>>=3; }}int enpre(int *pre,int m){ int cnt=1; memset(ch,-1,sizeof(ch)); ch[0]=0; int st=0; for(int i=0;i<=m;i++) { if(ch[pre[i]]==-1)ch[pre[i]]=cnt++; pre[i]=ch[pre[i]]; st<<=3; st|=pre[i]; } st<<=3; st|=num; return st;}void shift(int *pre,int m){ for(int i=m;i>0;i--)pre[i]=pre[i-1]; pre[0]=0;}void dpblank(int i,int j,int cur){ int k,left,up; for(k=0;k<hm[cur].size;k++) { depre(pre,M,hm[cur].state[k]); left=pre[j-1]; up=pre[j]; if(left&&up) { if(left!=up) { pre[j-1]=pre[j]=0; for(int t=0;t<=M;t++) if(pre[t]==up) pre[t]=left; if(j==M)shift(pre,M); hm[cur^1].push(enpre(pre,M),hm[cur].dp[k]+maze[i][j]); } } else if(left||up) { int t; if(left)t=left; else t=up; if(maze[i][j+1]) { pre[j-1]=0; pre[j]=t; hm[cur^1].push(enpre(pre,M),hm[cur].dp[k]+maze[i][j]); } if(maze[i+1][j]) { pre[j-1]=t; pre[j]=0; hm[cur^1].push(enpre(pre,j==M?M-1:M),hm[cur].dp[k]+maze[i][j]); } if(num<2) { num++; pre[j-1]=pre[j]=0; hm[cur^1].push(enpre(pre,j==M?M-1:M),hm[cur].dp[k]+maze[i][j]); } } else { pre[j-1]=pre[j]=0; hm[cur^1].push(enpre(pre,j==M?M-1:M),hm[cur].dp[k]); if(maze[i][j+1]&&maze[i+1][j]) { pre[j-1]=pre[j]=13; hm[cur^1].push(enpre(pre,M),hm[cur].dp[k]+maze[i][j]); } if(num<2) { num++; if(maze[i][j+1]) { pre[j]=13; pre[j-1]=0; hm[cur^1].push(enpre(pre,M),hm[cur].dp[k]+maze[i][j]); } if(maze[i+1][j]) { pre[j-1]=13; pre[j]=0; hm[cur^1].push(enpre(pre,j==M?M-1:M),hm[cur].dp[k]+maze[i][j]); } } } }}void dpblock(int i,int j,int cur){ int k; for(k=0;k<hm[cur].size;k++) { depre(pre,M,hm[cur].state[k]); pre[j-1]=pre[j]=0; if(j==M)shift(pre,M); hm[cur^1].push(enpre(pre,M),hm[cur].dp[k]); }}void init(){ scanf("%d%d",&N,&M); ans=0; memset(maze,0,sizeof(maze)); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) { scanf("%d",&maze[i][j]); if(maze[i][j]>ans)ans=maze[i][j]; }}void solve(){ int i,j,cur=0; hm[cur].init(); hm[cur].push(0,0); for(i=1;i<=N;i++) for(int j=1;j<=M;j++) { hm[cur^1].init(); if(maze[i][j])dpblank(i,j,cur); else dpblock(i,j,cur); cur^=1; } for(i=0;i<hm[cur].size;i++) if(hm[cur].dp[i]>ans) ans=hm[cur].dp[i]; printf("%dn",ans);}int main(){ int T; scanf("%d",&T); while(T--) { init(); solve(); } return 0;}