数字矩阵取数不相邻题解复盘基本信息项目内容题目编号、来源数字矩阵取数不相邻训练层级B DFS 回溯知识版块DFS、回溯、剪枝解题前・关键信号识别维度分析目标、约束、底层结构目标从 N×M 矩阵中取若干数字任意两个不相邻8 个方向求和最大约束N,M ≤ 6T ≤ 20底层结构每个格子选/不选DFS 逐格枚举所有方案。数据规模N×M ≤ 362^36 太大不能全枚举但 DFS 逐格 可行性剪枝可以过。候选算法和依据DFS 回溯依据每个格子只有选/不选两种状态按顺序逐格枚举选前检查 4 个方向是否冲突。复杂度预判最坏 O(2^(N×M))但剪枝后实际远小于N,M ≤ 6 能过。解题后・外化复盘维度内容实现结构 / 核心思路第一步从 (0,0) 开始 DFS逐格处理第二步对每个格子分两个分支不选直接去下一格和选检查 4 个方向后决定第三步选当前格子前检查左上、上、右上、左 4 个方向是否已被选若有冲突则不能选第四步若无冲突则标记 vis累加和递归下一格回溯撤销标记第五步所有格子处理完后更新最大值。核心思想按顺序逐格枚举选前只检查已处理过的 4 个方向。错因回溯1. 检查方向时用了continue而不是return没有循环所以编译错误2. 检查了 8 个方向多检查了还没处理的格子导致漏解3. 忘记回溯vis[x][y] false4. 边界判断写错导致数组越界。边界和易错点1. 只需要检查左上、上、右上、左 4 个方向因为按顺序遍历其他方向还没处理2. 用return结束冲突分支不是continue3. 回溯必须恢复vis4. 行末要换行处理if (y m) dfs(x1, 0, sum)5. 多组数据要重置 vis 数组。下次看到什么信号我应该想到这个方法看到「矩阵取数 不相邻 最大和 N,M≤6」用 DFS 逐格枚举 回溯。AC 完整代码#includeiostream#includealgorithm#includeset#includevectorusingnamespacestd;intv[10][10];boolvis[10][10];intans0;intn,m;voiddfs(intx,inty,intsum){if(ym){dfs(x1,0,sum);return;}if(xn){if(sumans)anssum;return;}dfs(x,y1,sum);if(x-10y-10vis[x-1][y-1])return;if(x-10vis[x-1][y])return;if(x-10y1mvis[x-1][y1])return;if(y-10vis[x][y-1])return;vis[x][y]true;dfs(x,y1,sumv[x][y]);vis[x][y]false;}intmain(){intt;cint;while(t--){cinnm;for(inti0;in;i){for(intj0;jm;j){cinv[i][j];vis[i][j]false;}}ans0;dfs(0,0,0);coutansendl;}return0;}