51nod1084 矩阵取数问题 V2

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();
	return x;
} 
const int nmax=205;
int a[nmax][nmax],dp[nmax][nmax][nmax<<1],n,m;
bool check(int x,int y){
	if(x<=0||x>n||y<=0||y>m) return 0;
	return 1;
}
int aa[5]={0,0,0,-1,-1};
int bb[5]={0,-1,-1,0,0};
int cc[5]={0,0,-1,0,-1};
int dd[5]={0,-1,0,-1,0};
void maxs(int &a,int b){
	if(a<b) a=b;
}
int main(){
	m=read(),n=read();
	rep(i,1,n) rep(j,1,m) a[i][j]=read();
	dp[1][1][1]=a[1][1];int ta,tb,u,v,d,o;
	rep(i,2,n+m-1){
		rep(j,1,min(i,n)) rep(k,1,min(i,n)){
			ta=i-j+1,tb=i-k+1;int &ts=dp[j][k][i];
			rep(t,1,4) {
				u=j+aa[t];v=ta+bb[t];d=k+cc[t];o=tb+dd[t];
				if(!check(u,v)||!check(d,o)) continue;
				maxs(ts,dp[u][d][i-1]);
			}
			if(j==k) ts+=a[j][ta];
			else ts+=a[j][ta]+a[k][tb];
		}
	}
	printf("%d\n",dp[n][n][n+m-1]);
	return 0;
}