虽然这题垃圾可以使用暴力解法,但实际上这个暴力也是可以大幅度优化的.原解法需要对共36个格子嵌套,即36层嵌套,实际上我们注意到在一个正方形的四个格子里要么全都不取,要么只能取一个(四种可能),共五种可能.那么我们就可以把原图分割为数个正方形,每次函数迭代就可以处理四个格子,最大进行32/4=8次嵌套.比原来的32次嵌套强了非常多.#include<bits/stdc++.h>

using namespace std;int b[10][10];
int a[10][10],n,m,t;
void f0(int x0,int y0,int c) {
    for(int x=max(x0-1,1);x<=min(x0+1,n);x++)
for(int y=max(y0-1,1);y<=min(y0+1,m);y++)b[x][y]+=c;
}
int f(int x0,int y0) {
if(x0>n){x0=1;y0+=2;}
if(y0>m)return 0;
int s=f(x0+2,y0);
for(int x=x0;x<=min(x0+1,n);x++)
for(int y=y0;y<=min(y0+1,m);y++) {
  if(b[x][y]==0){f0(x,y,1);;s=max(s,f(x0+2,y0)+a[x][y]);f0(x,y,-1);}
}
return s;
}
int main()
{
    cin>>t;
  while (t-->0) {
      cin>>n>>m;
      for(int i=1;i<=n;i++)
      for(int h=1;h<=m;h++){cin>>a[i][h];b[i][h]=0;}
      cout<<f(1,1)<<endl;
  }
    return 0;
}