取数游戏

#include <stdio.h>
#include <string.h>

int N, M;
int max_result;

// 解决函数：使用DFS搜索所有可能的选取方案
// matrix: 数字矩阵
// used: 标记哪些位置已经被选取
// x, y: 当前要处理的位置坐标
// sum: 当前已选取数字的总和
void solve(int matrix[N][M], int used[N][M], int x, int y, int sum) {
    // 如果已经处理完所有行，更新最大值并返回
    if (x >= N) {
        if (sum > max_result) max_result = sum;
        return;
    }
    
    // 计算下一个要处理的位置
    int next_x = x;
    int next_y = y + 1;
    // 如果当前行处理完了，移动到下一行的第一个位置
    if (next_y >= M) {
        next_x = x + 1;
        next_y = 0;
    }
    
    // 选择1：不选当前位置的数字
    // 直接跳到下一个位置，总和不变
    solve(matrix, used, next_x, next_y, sum);
    
    // 选择2：尝试选取当前位置的数字
    // 首先检查是否能选取（周围8个方向没有已选的数字）
    int can_choose = 1; // 假设可以选取
    
    // 检查周围8个方向（包括对角线）
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            // 跳过当前位置自身
            if (dx == 0 && dy == 0) continue;
            
            // 计算相邻位置的坐标
            int neighbor_x = x + dx;
            int neighbor_y = y + dy;
            
            // 检查相邻位置是否在矩阵范围内且已经被选取
            if (neighbor_x >= 0 && neighbor_x < N && 
                neighbor_y >= 0 && neighbor_y < M && 
                used[neighbor_x][neighbor_y]) {
                can_choose = 0; // 发现相邻位置已选，不能选当前位置
                break;
            }
        }
        // 如果已经确定不能选，提前结束检查
        if (!can_choose) break;
    }
    
    // 如果当前位置可以选取
    if (can_choose) {
        // 标记当前位置为已选取
        used[x][y] = 1;
        
        // 递归处理下一个位置，总和加上当前数字的值
        solve(matrix, used, next_x, next_y, sum + matrix[x][y]);
        
        // 回溯：取消当前位置的选取标记
        used[x][y] = 0;
    }
}

int main() {
    int T;
    scanf("%d", &T);
    
    // 处理每组测试数据
    while (T--) {
        // 读取矩阵大小
        scanf("%d %d", &N, &M);
        int matrix[N][M];    // 存储数字矩阵
        int used[N][M];      // 标记矩阵，记录哪些位置被选取
        
        // 初始化used数组为0（所有位置都未选取）
        memset(used, 0, sizeof(used));
        
        // 读取数字矩阵
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                scanf("%d", &matrix[i][j]);
            }
        }
        
        // 初始化最大结果为0
        max_result = 0;
        
        // 从矩阵的左上角(0,0)开始搜索
        solve(matrix, used, 0, 0, 0);
        
        // 输出最大和
        printf("%d\n", max_result);
    }
    return 0;
}