题解 | 取数游戏

// import java.util.Scanner;

// // 注意类名必须为 Main, 不要有任何 package xxx 信息
// public class Main {
//     public static void main(String[] args) {
//         Scanner in = new Scanner(System.in);
//         // 注意 hasNext 和 hasNextLine 的区别
//         // while (in.hasNextInt()) { // 注意 while 处理多个 case
//         //     int a = in.nextInt();
//         //     int b = in.nextInt();
//         //     System.out.println(a + b);
//         // } 21:42
//         // 1. 取出若干个数字
//         // 2. 取出若干个数字

//     }
// }

import java.util.Scanner;

public class Main {
    static int N, M;
    static int maxResult;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 测试用例数量

        while (T-- > 0) {
            N = scanner.nextInt(); // 矩阵行数
            M = scanner.nextInt(); // 矩阵列数

            int[][] matrix = new int[N][M]; // 存储数字矩阵
            int[][] used = new int[N][M];   // 标记矩阵（0=未选，1=已选）

            // 读取矩阵数据
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    matrix[i][j] = scanner.nextInt();
                }
            }

            maxResult = 0; // 初始化最大和为0
            solve(matrix, used, 0, 0, 0); // 从(0,0)开始搜索

            System.out.println(maxResult);
        }
        scanner.close();
    }

    /**
     * DFS搜索所有可能的选取方案
     * @param matrix 数字矩阵
     * @param used 标记矩阵（记录已选位置）
     * @param x 当前处理的行坐标
     * @param y 当前处理的列坐标
     * @param sum 当前已选取数字的总和
     */
    static void solve(int[][] matrix, int[][] used, int x, int y, int sum) {
        // 若处理完所有行，更新最大和并返回
        if (x == N) {
            if (sum > maxResult) {
                maxResult = sum;
            }
            return;
        }

        // 计算下一个要处理的位置
        int nextX = x;
        int nextY = y + 1;
        // 若当前行处理完毕，切换到下一行的第一个位置
        if (nextY >= M) {
            nextX = x + 1;
            nextY = 0;
        }

        // 选择1：不选当前位置，直接处理下一个位置
        solve(matrix, used, nextX, nextY, sum);

        // 选择2：尝试选取当前位置（需检查周围是否有已选位置）
        boolean canChoose = true;

        // 检查周围8个方向（上下左右及对角线）
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (dx == 0 && dy == 0) {
                    continue; // 跳过当前位置自身
                }

                // 计算相邻位置坐标
                int neighborX = x + dx;
                int neighborY = y + dy;

                // 检查相邻位置是否在矩阵范围内且已被选取
                if (neighborX >= 0 && neighborX < N
                        && neighborY >= 0 && neighborY < M
                        && used[neighborX][neighborY] == 1) {
                    canChoose = false;
                    break;
                }
            }
            if (!canChoose) {
                break; // 已确定不能选，提前结束检查
            }
        }

        // 若可以选取当前位置
        if (canChoose) {
            used[x][y] = 1; // 标记为已选
            // 递归处理下一个位置，总和加上当前数字
            solve(matrix, used, nextX, nextY, sum + matrix[x][y]);
            used[x][y] = 0; // 回溯：取消标记
        }
    }
}