双线DP
#include<iostream>
#include<algorithm>
#include<ctype.h>
#include<string>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
int dp[][][]; //压缩空间 dp[x1+y1][x1][x2];
//已知x1+y1 、x1和x2的值 ，结合x1 + y1 = x2 + y2 可以确定x1,y1,x2,y2四个值 int mp[][];
int max(int a,int b,int c,int d)
{
if(a>=b && a>=c && a>=d) return a;
else if(b>=a && b>=c && b>=d) return b;
else if(c>=a && c>=b && c>=d) return c;
else if(d>=a && d>=c && d>=b) return d;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int m,n;
cin>>m>>n;
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
cin>>mp[i][j];
}
}
int k,x1,y1,x2,y2;
for(k=;k<=m+n;k++)
for(x1=;x1<=m;x1++)
for(x2=;x2<=m;x2++)
dp[k][x1][x2] = ;
for(k=;k<=m+n;k++)
{
for(x1=;x1<=m;x1++) //(x,y)看作 其中一个坐标，结合k可求出对应的另一个点 ，遍历k和所有的(x,y) 就可以得到dp[k][x][y]的所有值
{
for(x2=;x2<=m;x2++)
{
y1 = k - x1;
y2 = k - x2; if( y1<=n && y2<=n && y1>= && y2>=) //不越界
{
if(x1 != x2 && y1 != y2) //不相交
{
int v1 = dp[k-][x1-][x2-] + mp[x1][y1] + mp[x2][y2];
int v2 = dp[k-][x1][x2] + mp[x1][y1] + mp[x2][y2];
int v3 = dp[k-][x1-][x2] + mp[x1][y1] + mp[x2][y2];
int v4 = dp[k-][x1][x2-] + mp[x1][y1] + mp[x2][y2];
dp[k][x1][x2] = max(v1,v2,v3,v4);
}
}
}
}
} cout<<dp[m+n-][m][m-]<<endl; } return ;
}