典型的dfs板子
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
int f[8][8];
int n;
int Max;
int ans;
int t, m;
bool st[8][8];
void dfs(int x, int y,int z)//表示选择到(x,y)这个顶点时的z为当前的最大值
{
//首先找出退出条件,当我们全部访问完这个点的时候,我们就会直接退出
if (x > t)
{
ans = max(ans, z);//比较一下当前的ans和z的大小,来找到最大值
return;
}
int next_y = y + 1;
int next_x = x;
if (next_y > m)
{
next_x++;
next_y = 1;
}
if (!st[x - 1][y] && !st[x - 1][y + 1] && !st[x - 1][y - 1] && !st[x][y + 1] && !st[x][y - 1] && !st[x + 1][y] && !st[x + 1][y + 1] && !st[x + 1][y - 1])
{
st[x][y] = true;
dfs(next_x, next_y, z + f[x][y]);
st[x][y] = false;
}
//如果这个点周围已经被访问的话,我们就不访问这个点,或者还有一种情况就是这个点周围没有访问的点,但是这个点我也不想访问
dfs(next_x, next_y, z);
}
int main()
{
cin >> n;
for (int i = 1; i <=n; i++)
{
cin >> t >> m;
//将原来的st全部重置
memset(st, false, sizeof st);
ans = 0;
for (int i = 1; i <= t; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> f[i][j];
}
}
dfs(1, 1, 0);
cout << ans << endl;
}
return 0;
}