1 #include<bits/stdc++.h>  2 using namespace std;  3 typedef long long ll;  4 const int MAXN=10;  5 const int MAXM=105;  6 const int HASH=30007;  7 const int INF=0x7fffffff;  8 ll ans=-1ll << 60;  9 int n,m,sat[MAXM][MAXN]; 10 int code[MAXN]; 11  12 struct HashMap 13 { 14     vector<int> hash[HASH]; 15     vector<ll> state,f; 16      17     void clear() 18     { 19         for(int i=0;i<HASH;i++) vector<int>().swap(hash[i]); 20         vector<ll>().swap(state); 21         vector<ll>().swap(f); 22     } 23      24     void push(ll st,ll ans) 25     { 26         int h=st%HASH; 27         for (int i=0;i<hash[h].size();i++) 28         { 29             int now=hash[h][i]; 30             if (state[now]==st) 31             { 32                 f[now]=max(f[now],ans); 33                 return; 34             } 35         } 36         state.push_back(st); 37         f.push_back(ans); 38         hash[h].push_back(state.size()-1); 39     } 40 }dp[2]; 41  42 void decode(ll state) 43 { 44     memset(code,0,sizeof(code)); 45     for (int i=n;i>=0;i--) 46     { 47         code[i]=state&7; 48         state>>=3; 49     } 50 } 51  52 void shift() 53 { 54     for (int i=n;i>0;i--) code[i]=code[i-1]; 55     code[0]=0; 56 }  57  58 ll encode() 59 { 60     int ch[MAXN],cnt=0; 61     memset(ch,-1,sizeof(ch)); 62     ch[0]=0; 63     ll ret=0; 64     for (int i=0;i<=n;i++) 65     { 66         if (ch[code[i]]==-1) ch[code[i]]=++cnt; 67         code[i]=ch[code[i]]; 68         ret<<=3; 69         ret|=code[i]; 70     } 71     return ret; 72 } 73  74 void dpblank(int i,int j,int cur) 75 { 76     for (int k=0;k<dp[1-cur].state.size();k++) 77     { 78         decode(dp[1-cur].state[k]); 79         if (j==1)//把之前shift的写法改成这样写了，总之就过了，也不知道为什么orz  80         { 81             if (code[n]) continue; 82             shift(); 83         } 84         int left=code[j-1],up=code[j]; 85          86         if (left && up) 87         { 88             code[j-1]=code[j]=0; 89             if (left==up) 90             { 91                 if (encode()==0) ans=max(ans,dp[1-cur].f[k]+sat[i][j]); 92                 //注意和之前不一样的地方：如果已经封闭起来了就更新答案  93             } 94             else 95             { 96                 for (int t=0;t<=n;t++) if (code[t]==left) code[t]=up; 97                 dp[cur].push(encode(),dp[1-cur].f[k]+sat[i][j]); 98             } 99         }100         101         if ((left && (!up)) || (up && (!left)))102         {103             int t=left|up;104             code[j-1]=0;105             code[j]=t;106             dp[cur].push(encode(),dp[1-cur].f[k]+sat[i][j]);             107             code[j-1]=t;108             code[j]=0;109             dp[cur].push(encode(),dp[1-cur].f[k]+sat[i][j]);110         }111         112         if (!left && !up)113         { 114             dp[cur].push(encode(),dp[1-cur].f[k]);115             //注意并不一定是所有格子都要经过，所以还要考虑不经过当前格子的情况 116             code[j-1]=code[j]=MAXN-1;117             dp[cur].push(encode(),dp[1-cur].f[k]+sat[i][j]);118         }119     }120 }121 122 void init()123 {124     scanf("%d%d",&m,&n);125     for (int i=1;i<=m;i++)126         for (int j=1;j<=n;j++) scanf("%d",&sat[i][j]);127 }128 129 void solve()130 {131     int cur=0;132     dp[cur].clear();133     dp[cur].push(0,0);134     for (int i=1;i<=m;i++)135         for (int j=1;j<=n;j++)136         {137             cur^=1;138             dp[cur].clear();139             dpblank(i,j,cur);140         }141     printf("%lld",ans);142 }143 144 int main()145 {146     init();147     solve();148     return 0;149 }