leetcode 1349

问题

Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character.

Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible..

Students must be placed in seats in good condition.

Example 1:

img

1
2
3
4
5
Input: seats = [["#",".","#","#",".","#"],
                [".","#","#","#","#","."],
                ["#",".","#","#",".","#"]]
Output: 4
Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.

Example 2:

1
2
3
4
5
6
7
Input: seats = [[".","#"],
                ["#","#"],
                ["#","."],
                ["#","#"],
                [".","#"]]
Output: 3
Explanation: Place all students in available seats.

Example 3:

1
2
3
4
5
6
7
Input: seats = [["#",".",".",".","#"],
                [".","#",".","#","."],
                [".",".","#",".","."],
                [".","#",".","#","."],
                ["#",".",".",".","#"]]
Output: 10
Explanation: Place students in available seats in column 1, 3 and 5.

Constraints:

  • seats contains only characters '.' and``'#'.
  • m == seats.length
  • n == seats[i].length
  • 1 <= m <= 8
  • 1 <= n <= 8

分析

使用状态压缩的DP算法进行逐行处理， f[i][j] 表示第 i 行的安排为 j 状态时前 i 排能够最多安排多少学生。其中 j 使用二进制数进行表示，如 10000001 表示该行的第一个位置和最后一个位置安排学，其他位置不安排学生。有状态转移方程。
$$
f[i][j] = max\{f[i-1][k]\} + popcnt(j) \; (j\&position[i] == j \;\&\& \;j|k \in S)
$$
其中 popcnt(j) 表示计算出 j 的二进制表示中 bit 位是1的个数，position[i] 表示第 i 行中由于椅子好坏的原因允许安排学生的情况，如第 i。行为，["#",".","#","#",".","#"]，则 position[i] 为 010010，集合 S 表示所有的二进制表示中没有两个相邻的bit是1的集合。

目标：$ max\{f[n-1][]\}$，

初始条件 $f[0][k] == popcnt(k) \; (k\&position[0] == k \; \&\& \;k \in S)$，其他 $ f[i][j] = -INF$。

代码

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
36
37
38
39
40
41
42
43
44
// 0 ms

class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int m = seats.size();
        int n = m==0? 0: seats[0].size();
        vector<vector<int>> dp(m, vector<int>((1<<n), INT_MIN));

        for (int i = 0; i < m; ++i) {
            int p = getSeats(seats[i]);
            for (int j = 0; j < (1<<n); ++j) {
                if ((p&j) != j) continue;
                if (i == 0) {
                    // 优化 in_s
                    if ((j & (j << 1)) == 0)  // (in_s[j] == true)
                        dp[i][j] = __builtin_popcount(j);
                } else {
                    for (int k = 0; k < (1<<n); ++k) {
                        if ((j|k) & ((j|k) << 1))
                            continue;
                        dp[i][j] = max(dp[i][j], dp[i-1][k]);
                    }
                    dp[i][j] += __builtin_popcount(j);
                }
            }
        }

        int ans = INT_MIN;
        for (int j = 0; j < (1<<n); ++j) {
            ans = max(ans, dp[m-1][j]);
        }
        return ans<0? 0: ans;
    }
    
    inline int getSeats(vector<char> &seat) {
        int ret = 0;
        for (int i = 0; i < seat.size(); ++i) {
            ret = ret<<1;
            ret += seat[i]=='#'? 0: 1;
        }
        return ret;
    }
};