P1123 取数游戏【洛谷算法习题】

P1123 取数游戏网页链接P1123 取数游戏题目描述一个N × M N\times MN×M的由非负整数构成的数字矩阵你需要在其中取出若干个数字使得取出的任意两个数字不相邻若一个数字在另外一个数字相邻8 88个格子中的一个即认为这两个数字相邻求取出数字和最大是多少。输入格式第一行有一个正整数T TT表示了有T TT组数据。对于每一组数据第一行有两个正整数N NN和M MM表示了数字矩阵为N NN行M MM列。接下来N NN行每行M MM个非负整数描述了这个数字矩阵。输出格式共T TT行每行一个非负整数输出所求得的答案。输入输出样例 #1输入 #13 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输出 #1271 172 99说明/提示样例解释对于第一组数据取数方式如下[ 67 ] 75 63 10 29 29 [ 92 ] 14 [ 21 ] 68 71 56 8 67 [ 91 ] 25 \begin{matrix} [67] 75 63 10 \\ 29 29 [92] 14 \\ [21] 68 71 56 \\ 8 67 [91] 25 \\ \end{matrix}[67]29[21]8​75296867​63[92]71[91]​10145625​数据范围及约定对于20 % 20\%20%的数据1 ≤ N , M ≤ 3 1\le N, M \le 31≤N,M≤3对于40 % 40\%40%的数据1 ≤ N , M ≤ 4 1\le N, M\le 41≤N,M≤4对于60 % 60\%60%的数据1 ≤ N , M ≤ 5 1\le N, M\le 51≤N,M≤5对于100 % 100\%100%的数据1 ≤ N , M ≤ 6 1\le N, M\le 61≤N,M≤61 ≤ T ≤ 20 1\le T\le 201≤T≤20a i , j ≤ 10 5 a_{i,j}\le10^5ai,j​≤105。解题思路本题是小范围网格最大独立集问题因N 、 M ≤ 6 N、M≤6N、M≤6数据规模极小采用DFS回溯枚举所有合法取数方案。按行优先顺序遍历矩阵每个格子对每个格子分两种决策不选取当前格子直接递归下一格选取当前格子则先检查八邻域无选中格子标记选中状态并累加数值后递归递归结束回溯恢复状态。遍历过程中实时维护全局最大取数和多组测试数据独立重置状态后求解。该方法暴力枚举所有合法方案逻辑简单直观完全适配题目极小的数据规模可快速得到最优解。总结核心逻辑D F S DFSDFS回溯枚举格子的选/不选通过八邻域校验保证取数不相邻求取数和最大值。关键操作递归遍历网格选数前检查8 88个相邻位置回溯恢复标记状态实时更新最大和。效率保障网格规模限制在6 × 6 6×66×6以内回溯枚举无冗余计算高效处理所有测试用例。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll p1e97;constll INF1e18;constll M2e310;ll n,m,ans,mp[10][10];boolv[10][10];boolcheck(ll x,ll y){if(v[x][y1]0v[x][y-1]0v[x1][y]0v[x1][y1]0v[x1][y-1]0v[x-1][y]0v[x-1][y1]0v[x-1][y-1]0)return1;return0;}voiddfs(ll x,ll y,ll z){ansmax(ans,z);ll xxx;ll yyy1;if(yym){xxx1;yy1;if(xxn)return;}if(check(xx,yy)){v[xx][yy]1;dfs(xx,yy,zmp[xx][yy]);v[xx][yy]0;}dfs(xx,yy,z);}intmain(){ll t;cint;while(t--){ans0;memset(v,0,sizeof(v));cinnm;for(ll i1;in;i)for(ll j1;jm;j)cinmp[i][j];v[1][1]1;dfs(1,1,mp[1][1]);memset(v,0,sizeof(v));dfs(1,1,0);coutansendl;}return0;}