175场周赛

5335. 参加考试的最大学生数

给你一个 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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func maxStudents(_ seats: [[Character]]) -> Int {
    let R = seats.count, C = seats[0].count
    var validity = [Int]()
    for i in 0..<R {
        var cur = 0
        for j in 0..<C {
            cur = 2*cur + (seats[i][j] == "." ? 1 : 0)
        }
        validity.append(cur)
    }
    func oneCount(_ n: Int) -> Int {
        var n = n
        var ct = 0
        while n > 0 {
            n = n & (n-1)
            ct += 1
        }
        return ct
    }
    var dp = [[Int]](repeating: [Int](repeating: -1, count: 1<<C), count: R+1)
    dp[0][0] = 0
    for i in 1...R {
        let valid = validity[i-1]
        for j in 0..<(1<<C) {
            if (j&valid == j) && (j&(j>>1) == 0) { // 确保mask为j时当前行的是合法的
                for k in 0..<(1<<C) where dp[i-1][k] != -1  { //确保mask为k时上一行是合法的
                    if (j&(k>>1) == 0) && ((j>>1)&k == 0) {  //确保当前行不与上一行冲突
                        dp[i][j] = max(dp[i][j], dp[i-1][k] + oneCount(j))
                    }
                }
            }
        }
    }
    return dp[R].max()!
}