参加考试的最大学生数

标签: 位运算 数组 动态规划 状态压缩 矩阵

难度: Hard

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。

学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。

学生必须坐在状况良好的座位上。

示例 1：

输入：seats = [["#",".","#","#",".","#"],
              [".","#","#","#","#","."],
              ["#",".","#","#",".","#"]]
输出：4
解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。

示例 2：

输入：seats = [[".","#"],
              ["#","#"],
              ["#","."],
              ["#","#"],
              [".","#"]]
输出：3
解释：让所有学生坐在可用的座位上。

示例 3：

输入：seats = [["#",".",".",".","#"],
              [".","#",".","#","."],
              [".",".","#",".","."],
              [".","#",".","#","."],
              ["#",".",".",".","#"]]
输出：10
解释：让学生坐在第 1、3 和 5 列的可用座位上。

提示：

  • seats 只包含字符 '.' 和'#'
  • m == seats.length
  • n == seats[i].length
  • 1 <= m <= 8
  • 1 <= n <= 8

Submission

运行时间: 30 ms

内存: 16.5 MB

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        a = [sum((c == '.') << j for j, c in enumerate(s)) for s in seats]
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if j == 0:
                return dfs(i - 1, a[i - 1] & ~(k << 1 | k >> 1), 0) if i else 0
            lb = j & -j
            return max(dfs(i, j ^ lb, k), dfs(i, j & ~(lb * 3), k | lb) + 1)
        return dfs(len(seats) - 1, a[-1], 0)

Explain

该题解采用动态编程与位运算相结合的方法来求解。首先，将教室的座位状态从字符数组转换为整数数组，每个整数的二进制位表示一行中的座位是否可用（'.' 表示可用，对应位为1）。接着，定义一个递归函数 `dfs` 来尝试所有可能的座位安排。对于每一行，递归函数尝试将学生放在当前可用的座位上，同时确保不违反学生之间的视线要求（不能看到左上、右上、左边、右边的同学）。`dfs` 函数使用记忆化以避免重复计算，提高效率。最终，通过递归检查所有行的所有可能座位安排，找出可以容纳的最大学生数。

时间复杂度: O(m * 4^n)

空间复杂度: O(m * 4^n)

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        # 将座位转换为行的整数表示，1 代表可用座位
        a = [sum((c == '.') << j for j, c in enumerate(s)) for s in seats]
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            # 处理边界条件
            if j == 0:
                return dfs(i - 1, a[i - 1] & ~(k << 1 | k >> 1), 0) if i else 0
            # 找到 j 中最低位的1
            lb = j & -j
            # 选择不在当前位置放学生或放学生两种情况
            return max(dfs(i, j ^ lb, k), dfs(i, j & ~(lb * 3), k | lb) + 1)
        # 从最后一行开始尝试放置学生
        return dfs(len(seats) - 1, a[-1], 0)

Explore

`i`代表当前正在处理的行的索引，`j`代表当前行中尚未被选择的可用座位的集合（以二进制形式表示，1代表该位置可用），`k`代表上一行中已经放置学生的座位（同样以二进制形式表示）。在递归中，当函数考虑当前行的一个座位时，将这个座位从`j`中移除。如果选择在这个座位放置学生，则更新`k`来包含这个座位（通过`k | lb`操作），且在下一次调用中，不考虑当前座位及其邻近座位（通过`j & ~(lb * 3)`操作）。当一行处理完毕后，递归调用转向上一行（`i`递减），同时重置`j`为上一行的初始可用座位状态，并继续尝试不同的座位组合。

`k << 1`和`k >> 1`分别将`k`中表示上一行学生座位的二进制位向左和向右移动一位，这模拟了检查当前座位的左上和右上位置是否有学生。这种位移操作确保了学生之间不会相互干扰视线。尽管这种检查仅限于左上和右上的座位，递归函数在处理当前行时也会考虑当前座位左边和右边的约束（通过`j & ~(lb * 3)`操作，禁止相邻座位同时被选用），从而确保左右方向的座位约束也被适当处理。

记忆化存储是通过使用`@cache`装饰器实现的，这是Python标准库中的功能，属于`functools`模块。`@cache`装饰器会自动存储函数的输入参数与对应的输出结果。当这个函数再次被相同的输入参数调用时，不会重新计算函数体，而是直接从缓存中返回之前存储的结果。这样可以显著减少重复计算，特别是在递归函数中处理重叠子问题时非常有效，从而提高整体的计算效率。