P1123取数游戏

题目描述 一个 N×M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 8 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

输入格式 第一行有一个正整数 T，表示了有 T 组数据。

对于每一组数据，第一行有两个正整数 N 和 M，表示了数字矩阵为 N 行 M 列。

接下来 N 行，每行 M 个非负整数，描述了这个数字矩阵。

输出格式 共 T 行，每行一个非负整数，输出所求得的答案。

#include <iostream> using namespace std; int T, n, m, a[2000][2000]; int ans; int u[2000][20000]; void dfs(int x, int y, int z) { if (x > n) { ans = max(ans, z); return ; } int next_x = x, next_y = y + 1; if (next_y > m) { next_y = 1; next_x = x + 1; } if (!u[x - 1][y - 1] && !u[x - 1][y] && !u[x - 1][y + 1] && !u[x][y - 1] && !u[x][y + 1] && !u[x + 1][y - 1] && !u[x + 1][y] && !u[x + 1][y + 1]) { u[x][y] = 1; dfs(next_x, next_y, z + a[x][y]); u[x][y] = 0; } dfs(next_x, next_y, z); } int main() { //std::ios::sync_with_stdio(false); cin >> T; for (int sth = 1; sth <= T; ++sth) { ans = 0; cin >> n >> m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> a[i][j]; dfs(1, 0, 0); cout << ans << endl; } return 0; }