【洛谷DFS算法】P1123取数游戏
本题要求从一个 N×M 的非负整数矩阵中取出若干个数字，使得取出的任意两个数字不相邻（相邻指的是在 8 个方向相邻），并求出取出数字和的最大值。可以使用深度优先搜索（DFS）的方法来遍历矩阵中所有可能的取数组合，找出满足条件的最大和。
【算法思路】
-
输入处理：读取测试用例的数量 T，对于每个测试用例，读取矩阵的行数 N 和列数 M，以及矩阵中的元素。
初始化标记数组：每次处理一个测试用例或开始新的 DFS 时，必须将 visited 数组初始化为全 false，保证不同起点的独立性，避免标记残留何错误结果
-
可行性剪枝：
- 定义当前要检查位置的行列坐标（x,y）
- 用八方向偏移数组计算当前位置（x,y）第 i 个相邻位置的坐标。
- for循环遍历相邻位置：条件姚确保计算得到的相邻位置的行坐标
nx在矩阵的有效范围内（行数从0到n-1，列数从0到m-1）,以及用bool变量检查相邻位置是否已经被标记为取过数 return true:如果循环完8个相邻位置，都没有发现有位置已经取过数，说明当前位置（x,y）可以取数，函数返回true
-
深度优先搜索：从矩阵的左上角开始，对于每个位置，有两种选择：取该位置的数字或者不取。在取数字时，需要检查该位置的 8 个相邻位置是否已经取过数字，如果相邻位置都没有取过数字，则可以取该位置的数字，并标记该位置已取。
①问题抽象与状态表示：该问题本质上是一个组合搜索问题，需要在矩阵的所有可能数字组合中找出满足 “任意两个数字不相邻” 这一条件且数字和最大的组合。
状态表示：使用深度优先搜索时，需要明确每一个搜索状态。在这个问题中，一个搜索状态可以由当前正在考虑的矩阵位置（用行坐标
x和列坐标y表示）以及到目前为止已经选取的数字的总和curSum来表示。因此，dfs函数的参数设计为dfs(int x, int y, int curSum)。②确定递归终止条件
在深度优先搜索中，需要明确何时停止递归。当搜索完矩阵的所有元素时，就完成了一种取数组合的尝试，此时可以对该组合的数字和进行评估。具体来说，当 x 等于矩阵的行数 n 时，表示已经遍历完矩阵的所有行，此时可以更新最大数字和 maxSum，并结束当前递归调用。
③计算下一个搜索状态
在处理完当前位置 (x, y) 后，需要确定下一个要考虑的位置。通常按照从左到右、从上到下的顺序遍历矩阵。因此，先尝试将列坐标 y 加 1，如果 y 达到矩阵的列数 m，则表示到达当前行的末尾，需要换到下一行的第一列，即行坐标 x 加 1，列坐标 y 重置为 0。
④枚举选择分支
- 不取当前位置的数字：直接递归调用
dfs函数，传入下一个位置的坐标(nextX, nextY)和当前的取数总和curSum，继续考虑下一个位置的取数情况。 - 取当前位置的数字：在取当前位置的数字之前，需要检查该位置是否可以取数，即该位置的 8 个相邻位置是否已经有数字被取过。可以使用一个辅助函数 canTake(x, y) 来进行检查。如果可以取数，则将该位置标记为已取，更新取数总和 curSum 并递归调用 dfs 函数继续搜索。在递归调用返回后，需要进行回溯操作，将该位置的标记撤销，以便尝试其他可能的取数组合
⑤剪枝优化：
canTake函数实际上起到了剪枝作用 - 不取当前位置的数字：直接递归调用
-
回溯：在搜索完一个位置的所有可能情况后，需要回溯，即撤销该位置的取数标记，以便尝试其他可能的取数组合。
-
记录最大值：在搜索过程中，记录能取到的最大数字和。
【代码示例】
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 7;
int n, m;
vector<vector<int>> grid(MAXN, vector<int>(MAXN));
bool visited[MAXN][MAXN];
int maxSum = 0;
// 检查 (x, y) 位置的 8 个相邻位置是否有数字被取过
bool canTake(int x, int y) {
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
for (int i = 0; i < 8; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny]) {
return false;
}
}
return true;
}
// 深度优先搜索函数
void dfs(int x, int y, int curSum) {
if (x == n) {
maxSum = max(maxSum, curSum);
return;
}
int nextX = x, nextY = y + 1;
if (nextY == m) {
nextX++;
nextY = 0;
}
// 不取当前位置的数字
dfs(nextX, nextY, curSum);
// 若可以取当前位置的数字，则取
if (canTake(x, y)) {
visited[x][y] = true;
dfs(nextX, nextY, curSum + grid[x][y]);
visited[x][y] = false;
}
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n >> m;
// 读取矩阵
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}
maxSum = 0;
// 初始化访问标记数组
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
visited[i][j] = false;
}
}
// 从 (0, 0) 位置开始深度优先搜索
dfs(0, 0, 0);
cout << maxSum << endl;
}
return 0;
}
max(a,b)：C++ 标准库函数（定义在 头文件中），返回两个参数中的较大值。
【方向偏移数组】
在二维平面中，每个位置通常用一对坐标
(x, y)表示。当我们需要从一个位置移动到它的相邻位置时，相邻位置的坐标与当前位置的坐标存在一定的偏移关系。方向偏移数组就是用来存储这些偏移量的数组。遍历相邻位置：在处理二维网格问题时，经常需要遍历某个位置的相邻位置，例如在深度优先搜索（DFS）、广度优先搜索（BFS）、路径查找等算法中。使用方向偏移数组可以方便地计算出相邻位置的坐标。
简化代码：避免在代码中重复编写计算相邻位置坐标的逻辑，使代码更加简洁、易读和可维护。