不用考虑走的方法，因为一旦合法，即不同时取相邻的两个，一定能达到。
所以只用考虑怎么取就行了。
把棋盘黑白染色，S到黑点建权值为val的边，白点到T建权值为val的边，
然后把相邻的黑白点建一条为inf的边。
求最小割。
不得不提一句：边从零开始建和从一开始建一个wa一个a。。
^时相应的正边和反边必须对应。（卡了好久，身败名裂）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
#define inf 100000000
using namespace std;
int n,m,a[505][505],b[505][505],S=0,T,cnt,c[505][505];
int dep[100005],e,adj[100005],sum=0;
struct node
{
int v,l,next;
} lu[100005];
void add(int u,int v,int l)
{lu[e].v=v;lu[e].l=l;lu[e].next=adj[u];adj[u]=e++;}
inline int bfs()
{
memset(dep,0,sizeof(dep));
queue<int> q;
dep[S]=1;
q.push(S);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=adj[x];i!=-1;i=lu[i].next)
{
int to=lu[i].v;
if(lu[i].l&&!dep[to])
{
dep[to]=dep[x]+1;
q.push(to);
if(to==T)return 1;
}
}
}
return 0;
}
inline int read()
{
int su=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch<='9'&&ch>='0'){su=su*10+ch-'0';ch=getchar();}
return su;
}
inline int dfs(int now,int f){
if(now==T){
return f;
}
int tmp=f;
for(int i=adj[now];i!=-1;i=lu[i].next){
int to=lu[i].v,w=lu[i].l;
if(w&&tmp&&dep[to]==dep[now]+1){
int k=dfs(to,min(w,tmp));
if(!k){
dep[to]=0;
continue;
}
lu[i].l-=k;
lu[i^1].l+=k;
tmp-=k;
}
}
return f-tmp;
}
int yjn()
{
freopen("Excalibur.in","r",stdin);
freopen("Excalibur.out","w",stdout);
scanf("%d%d",&n,&m);
memset(adj,-1,sizeof(adj));
for(int i=1;i<=n;i++)
{
int k=0;
if(i&1)k=1;
for(int j=1;j<=m;j++)
{
a[i][j]=++cnt;
b[i][j]=k;k^=1;
c[i][j]=read();
sum+=c[i][j];
}
}
/* for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<b[i][j]<<" ";
cout<<endl;
}*/
T=cnt+3;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(b[i][j])
{add(a[i][j],T,c[i][j]),add(T,a[i][j],0);}
else
{add(S,a[i][j],c[i][j]),add(a[i][j],S,0);}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(b[i][j]==0)
{
if(i!=1){add(a[i][j],a[i-1][j],inf),add(a[i-1][j],a[i][j],0);}
if(i!=n){add(a[i][j],a[i+1][j],inf),add(a[i+1][j],a[i][j],0);}
if(j!=1){add(a[i][j],a[i][j-1],inf),add(a[i][j-1],a[i][j],0);}
if(j!=m){add(a[i][j],a[i][j+1],inf),add(a[i][j+1],a[i][j],0);}
}
}
int ans=0;
while(bfs())
ans+=dfs(S,inf);
cout<<(sum-ans);
}
int qty=yjn();
int main(){;}