首页 > 试题广场 >

取数游戏

[编程题]取数游戏

热度指数：3392 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

${\hspace{15pt}}$ 一个 $N\times M$ 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 $8$ 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

输入描述:

第一行有一个正整数 （），表示了有  组数据。

对于每一组数据，第一行有两个正整数 （），表示了数字矩阵为  行  列。

接下来  行，每行  个非负整数，描述了这个数字矩阵，满足 。

输出描述:

输出共  行，每行一个非负整数，输出所求得的答案。

示例1

输入

输出

算法知识视频讲解

Python3

juo1

每一行当作一个bitmask, 表示这个一行取哪些元素

然后下一行取什么完全取决于上一行：确认垂直和对角不相邻

def solve():
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]

    # 1. Precompute all masks that are valid within a single row
    valid_masks = []
    for mask in range(1 << m):
        if not (mask & (mask << 1)):
            valid_masks.append(mask)

    memo = {}

    def dp(row_idx, prev_mask):
        if row_idx == n:
            return 0
        
        state = (row_idx, prev_mask)
        if state in memo: return memo[state]

        res = 0
        for curr_mask in valid_masks:
            # 2. Check compatibility with the PREVIOUS row (8-neighbors)
            # Vertical check
            if (curr_mask & prev_mask): continue
            # Diagonal checks
            if (curr_mask & (prev_mask << 1)): continue
            if (curr_mask & (prev_mask >> 1)): continue
            
            # 3. Calculate sum for this row configuration
            current_row_sum = 0
            for i in range(m):
                if (curr_mask >> i) & 1:
                    current_row_sum += grid[row_idx][i]
            
            # Recurse to next row
            res = max(res, current_row_sum + dp(row_idx + 1, curr_mask))
        
        memo[state] = res
        return res

    # Start at row 0 with a '0' mask for the non-existent row -1
    print(dp(0, 0))


for _ in range(int(input())):
    solve()

发表于 2026-03-06 00:09:54 回复(0)