题解 | #取数游戏#

1. 思路非常清晰的一个dfs题目，但是要注意dfs的遍历方式。dfs的时候不要每次都从头开始，而是要想遍历一行数组一样不回头；也就是dfs当前层要基于上一层进行顺序遍历，而不是继续从头(0，0)节点重新遍历。
2. 首先说明，以上两种方法都能得到正确的值，区别在于“从头遍历”的方法会超时。
3. 为什么效果一样呢？因为“从头遍历法”中存在很多重复的。比如浅层dfs到深层dfs这种case会在深层dfs时由于“从头遍历”而再次遇到浅层dfs中访问过的点。
4. 具体的“层层递进的dfs法”写法如下：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int group = in.nextInt();
        for (int i = 0; i < group; i++) {
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] matrix = new int[n][m];
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    matrix[j][k] = in.nextInt();
                }
            }
            boolean[][] visited = new boolean[n][m];
            dfs(matrix, visited, 0, 0, 0);
            System.out.println(MaxSum);
            MaxSum = 0;
        }
    }

    public static int MaxSum = 0;


    public static int[][] closeDirections = new int[][] {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

    // 层层递进的dfs
    public static void dfs(int[][] matrix, boolean[][] visited, int i, int j,
                           int curSum) {
        if (i >= visited.length) {
            // 访问完了
            return;
        }
        int nextI = i;
        int nextJ = j + 1;
        if (nextJ >= visited[0].length) {
            nextJ = 0;
            nextI++;
        } 
        // 不选中当前位置
        dfs(matrix, visited, nextI, nextJ, curSum);
        boolean canV = true;
        for (int[] closeDirection : closeDirections) {
            int neighborX = i + closeDirection[0];
            int neighborY = j + closeDirection[1];
            if (neighborX < 0 || neighborX >= visited.length || neighborY < 0 ||
                    neighborY >= visited[i].length) {
                continue;
            }
            if (visited[neighborX][neighborY]) {
                canV = false;
                break;
            }
        }
        if (canV) {
            // 选中当前位置
            visited[i][j] = true;
            int newSum = curSum + matrix[i][j];
            MaxSum = Math.max(MaxSum, newSum);
            dfs(matrix, visited, nextI, nextJ, newSum);
            // 回溯
            visited[i][j] = false;

        }


    }
}