题目描述
一个 N×M 的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻 8 个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。
输入格式
第一行有一个正整数 T,表示了有 T组数据。
对于每一组数据,第一行有两个正整数 N和 M,表示了数字矩阵为 N行 M列。
接下来 N行,每行 M个非负整数,描述了这个数字矩阵。
输出格式
共 T行,每行一个非负整数,输出所求得的答案。
样例
3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1
271
172
99(竖着排的)
算法:dfs
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=12;
int g[N][N];
int sum,m,n;
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
bool st[N][N];
void dfs(int x,int y,int s)
{
if(y==m+1)//边界情况
{
dfs(x+1,1,s);
return;//边界情况加return
}
if(x==n+1)//边界情况
{
sum=max(sum,s);
return;
}
//不要:
dfs(x,y+1,s);
//要:
bool ok=true;
for(int i=0;i<8;i++)//8个位置的遍历
{
int x1=x+dx[i],y1=y+dy[i];
if(x1<1||y1<1||x1>n||y1>m) continue;//如果这个点在矩阵外面,就跳过下面的
if(st[x1][y1])
{
ok=false;
break;
}
}
if(ok)
{
st[x][y]=true;
dfs(x,y+1,s+g[x][y]);
st[x][y]=false;//回溯
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
dfs(1,1,0);
cout<<sum<<endl;
sum=0;
memset(g,0,sizeof g);
}
return 0;
}