代码

#include<bits/stdc++.h>
using namespace std;
int n,m,p[150][150],res[10][10],ans,t;
int dir[8][2]={-1,0,1,0,0,-1,0,1,-1,-1,-1,1,1,1,1,-1};
bool pd(int x,int y){
	return 1<=x&&x<=n&&1<=y&&y<=m;
}
inline void check(){
	int sum=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(res[i][j]==1){
				sum+=p[i][j];
				for(int k=0;k<8;k++){
					int cx=i+dir[k][0],cy=j+dir[k][1];
					if(pd(cx,cy)&&res[cx][cy]==1)return;
				}
			}
		}
	}
	ans=max(ans,sum);
}
inline void dfs(int x,int y){
	if(y>m){
		x+=1;
		y=1;
	}
	if(x>n){
		check();
		return;
	}
	res[x][y]=0;
	dfs(x,y+1);
	res[x][y]=1;
	dfs(x,y+1);
}
int main(){
	cin>>t;
	while(t--){
		ans=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>p[i][j];
			}
		}
		dfs(1,1);
		cout<<ans<<endl;
	}
	return 0;
}

记录详情

求助，3个TLE，49分