题解 | 取数游戏

dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]

def in_bound(x:int, y:int, N:int, M:int):
    return 0 <= x < N and 0 <= y < M

def dfs(N:int, M:int, maze:list, used:list, curr_sum:int, start:int):
    global max_num
    flag = True
    for pos in range(start, N*M):
        i, j = divmod(pos, M)
        # 找到下一个没被用到的点
        if used[i][j] == -1:
            flag = False
            # 选中的点记为1
            used[i][j] = 1
            blocked = []
            # 周边点记为0
            for k in range(8):
                nx = i + dx[k]
                ny = j + dy[k]
                if in_bound(nx, ny, N, M) and used[nx][ny] == -1:
                    used[nx][ny] = 0
                    blocked.append((nx, ny))
            # 继续寻找
            dfs(N, M, maze, used, curr_sum + maze[i][j], pos + 1)
            # 回溯状态
            used[i][j] = -1
            for x, y in blocked:
                used[x][y] = -1
    if flag:
		# 没有点能再加入了
        max_num = max(max_num, curr_sum)

def calculate_num(N: int, M: int, maze: list):
    global max_num
    used = [[-1]*M for _ in range(N)]
    max_num = 0
    dfs(N, M, maze, used, 0, 0)
    return max_num

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    maze = [list(map(int, input().split())) for _ in range(N)]
    print(calculate_num(N, M, maze))