题解 | 取数游戏

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	nextInt := func() int {
		scanner.Scan()
		x, _ := strconv.Atoi(scanner.Text())
		return x
	}

	T := nextInt()
	for t := 0; t < T; t++ {
		N, M := nextInt(), nextInt()
		grid := make([][]int, N)
		for i := 0; i < N; i++ {
			grid[i] = make([]int, M)
			for j := 0; j < M; j++ {
				grid[i][j] = nextInt()
			}
		}

		// 访问数组，记录哪些格子已被选
		visited := make([][]bool, N)
		for i := range visited {
			visited[i] = make([]bool, M)
		}

		var maxSum int = 0

		// DFS 函数：从 (i, j) 开始搜索
		var dfs func(i, j, sum int)
		dfs = func(i, j, sum int) {
			// 判断是否到达最后一行或列
			if i == N {
				if sum > maxSum {
					maxSum = sum
				}
				return
			}
			nextI, nextJ := i, j+1
			if nextJ == M {
				nextI, nextJ = i+1, 0
			}

			// 选项1：不选当前格子
			dfs(nextI, nextJ, sum)

			// 选项2：选当前格子（如果合法）
			if !visited[i][j] {
				// 检查周围 8 个方向是否有已选的格子
				valid := true
				dx := []int{-1, -1, -1, 0, 0, 0, 1, 1, 1}
				dy := []int{-1, 0, 1, -1, 0, 1, -1, 0, 1}
				for k := 0; k < 9; k++ {
					ni, nj := i+dx[k], j+dy[k]
					if ni >= 0 && ni < N && nj >= 0 && nj < M && visited[ni][nj] {
						valid = false
						break
					}
				}
				if valid {
					visited[i][j] = true
					dfs(nextI, nextJ, sum+grid[i][j])
					visited[i][j] = false // 回溯
				}
			}
		}

		dfs(0, 0, 0)
		fmt.Println(maxSum)
	}
}