P1123 取数游戏

#include<bits/stdc++.h>
#define MAXN 8
using namespace std;
int t;
int n,m;
int a[MAXN][MAXN];
int ans;
struct xy
{
	int x,y;
};
queue<xy>q;
xy w[10]={{0,0},{0,1},{0,-1},{1,0},{1,-1},{1,1},{-1,0},{-1,1},{-1,-1}};
bool check(int i,int j)
{
	for(int ii=1;ii<=q.size();ii++)
	{
		for(int jj=1;jj<=8;jj++)
		{
			xy walk=w[jj];
			if(q.front().x+walk.x==i&&q.front().y+walk.y==j)
				return false;
		}
		q.push(q.front());
		q.pop();
	}
	return true;
}
void dfs(int i,int j,int cnt)
{
	if(i>n)
	{
		int sum=0;
		for(int i=1;i<=q.size();i++)
		{
			sum+=a[q.front().x][q.front().y];
			q.push(q.front());
			q.pop();
		}
		ans=max(ans,sum);
		return ;
	}
	if(check(i,j))
	{
		q.push({i,j});
		dfs(j==m?i+1:i,j==m?1:j+1,cnt+1);
		for(int p=1;p<q.size();p++)
		{
			q.push(q.front());
			q.pop();
		}
		q.pop();
	}
	dfs(j==m?i+1:i,j==m?1:j+1,cnt);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(a,0,sizeof(a));
		ans=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
		dfs(1,1,0);
		printf("%d\n",ans);
	}
	return 0;
}

[编译结果] (https://www.luogu.com.cn/record/74700305) 4WA2T