题解 | 取数游戏

#include <stdio.h>
int n, m;
int a[10][10];
int selected[10][10]; // 记录哪些格子被选中了
long long max_ans = 0;
// 检查 (r, c) 的 8 个方向是否有已经选中的数字
int check(int r, int c) 
{
    for (int i = r - 1; i <= r + 1; i++) 
    {
        for (int j = c - 1; j <= c + 1; j++) 
        {
            if (i >= 0 && i < n && j >= 0 && j < m) 
            {
                if (selected[i][j]) return 0; // 发现邻居已选，冲突
            }
        }
    }
    return 1; // 安全，可以选
}
void dfs(int r, int c, long long current_sum) 
{
    // 换行逻辑：如果当前列越界，转到下一行第一列
    if (c >= m) 
    {
        dfs(r + 1, 0, current_sum);
        return;
    }
    // 终止逻辑：所有行处理完毕
    if (r >= n) 
    {
        if (current_sum > max_ans) 
        {
            max_ans = current_sum;
        }
        return;
    }
    // --- 分支 1：不选当前的格 (r, c) ---
    dfs(r, c + 1, current_sum);
    // --- 分支 2：选当前的格 (r, c) ---
    if (check(r, c)) 
    {
        selected[r][c] = 1; // 标记选中
        dfs(r, c + 1, current_sum + a[r][c]);
        selected[r][c] = 0; // 回溯：撤销标记，供其他路径尝试
    }
}
int main() 
{
    int t;
    scanf("%d", &t);
    while (t--) 
    {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; j < m; j++) 
            {
                scanf("%d", &a[i][j]);
                selected[i][j] = 0;
            }
        }
        max_ans = 0;
        dfs(0, 0, 0);
        printf("%lld\n", max_ans);
    }
    return 0;
}