[LeetCode] 1349. Maximum Students Taking Exam #1349

grandyang · 2019-05-30T16:35:04Z

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:

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

Example 2:

Input: seats = [[".","#"],
["#","#"],
["#","."],
["#","#"],
[".","#"]]
Output: 3
Explanation: Place all students in available seats.

Example 3:

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

这道题说是给了一个 m by n 大小的矩阵，其中点 . 的位置表示好着的椅子，井字号 # 表示坏了的椅子，不能坐人。考生可以坐在好着的椅子上考试，说是考生可以看到其左右两边，以及左前方，右前方人的答案，为了防止作弊发生，上述四个位置不能坐人，问给定的矩阵最多可以坐多少个考生。博主最先看到这题时，感觉有点像八皇后问题的变形，矩阵就是个棋盘，每个考生就是削弱版的皇后，只能覆盖到左右，左前，右前四个位置。想到这，博主最先尝试的使用递归来做的，也就是遍历所有的情况，吭哧吭哧写好后，发现在超大 test case 上超时了，看了下没通过的测例，好多好多1连在一起，一般的递归可能会存在大量的重复计算，非常不高效。后来参考了网上各位大神们的解法，发现普遍都是用的位运算的思路，利用二进制当 mask 来表示特定的状态。比如用1表示好椅子，0表示坏椅子，那么对于例子1中的第一行 ["#",".","#","#",".","#"]，就可以用二进制数 010010 来表示，也就是十进制数 18，那么给定的矩阵每一行都可以用一个二进制来表示，这里使用一个数组 avail，其中 avail[i] 表示第i排的座位的二进制数的表示，注意这里从第一排开始算的，所以整个数组设定大小为9。下面来更新这个 avail 数组，一排一排的更新，对于第i排，遍历每一个位置，若该位置是好椅子，则将对应位置变为1，即'或'上 1<<j 即可。

接下来考虑考生坐的位置，这里考生坐的位置的状态也用二进制数来表示，1表示该位置有考生，0表示该位置没有考生，这里的二进制数跟椅子状态的二进制数是有关联的，因为考生必须要坐到好椅子上，好椅子则可以有考生，也可以没有考生。所以考生状态 mask 的位置1，一定对应的是椅子状态的1。为了遍历所所有的情况，先假定每个位置都能坐人，则对于n个座位的话，能坐人的不同情况为 1<<n 种，而每种情况就是 [0, 1<<n) 范围内的数字的二进制的 mask，由于总共有m排，所以可以用一个二维数组 dp，其中 dp[i][mask] 表示前i排安排了考生，且第i排安排考生的状态是 mask 的二进制表示的情况，最多能安排的考生个数。dp 数组的大小为 9 by 1<<8，则最终所求的即为一维数组 dp[m] 中的最大值。数组中每个数字先初始化 -1，然后再更新 dp[0] 的值，因为这里我们是从第一排开始算的，所以第0排没有意义，将 dp[0] 中所有值赋值为0。然后就要开始遍历第一排到第m排了，接下来就是难点了，要找到状态转移方程。对于任意第i排，我们此时应该是知道了第 i-1 排的情况，即所有的 dp[i-1][premask] 都是已经计算过了的，而第i排的 mask 其实是跟 premask 息息相关的，所以理应遍历 premask 的所有情况。

这里所有的 mask 的范围均为 [0, 1<<n)，对于遍历到的 premask，可以快速查看一下其 dp 值，若 dp[i-1][premask] 仍为 -1，说明该 premask 的情况是不正确的，直接跳过。否则就可以遍历第i排的所有 mask 的情况，对于遍历到的 mask，首先要确保安排考生的位置是好椅子，判断的方法是用 mask '与'上 avail[i]，只有考生和好椅子相同的位置上才能留下1，这样结果还是得到 mask，若得到的不是 mask 的情况，直接跳过。接下来还要判断 mask 中是否有连续1，因为考生能看到左右的答案，所以不能有相连的考生，即不能有连续1，判断的方法是 mask & (mask >> 1)，即用 mask '与'上其本身上右移一位的结果，若有连续1，则得到的结果不为0。最后还要判断其左上和右上是否有考生，判断左上的方法是用 mask '与'上 premask 右移一位的结果，即 mask & (premask >> 1)，同理，判断右上的方法是用 mask '与'上 premask 左移一位的结果，即 mask & (premask << 1)。若所有条件均满足的话，则可以用 dp[i - 1][premask] + countOnes(mask) 来更新 dp[i][mask] 了，我们需要写一个 countOnes 函数，用来统计二进制数 mask 中的1的个数，当然，有的人可能会偷懒用自带的 __builtin_popcount 函数。更新完了 dp 数组之后，只要找出 dp[m] 中最大的值即可，参见代码如下：

class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int m = seats.size(), n = seats[0].size(), res = 0, size = (1 << 8);
        vector<vector<int>> dp(9, vector<int>(size, -1));
        vector<int> avail(9);
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (seats[i - 1][j] == '.') {
                    avail[i] |= (1 << j);
                }
            }
        }
        for (int mask = 0; mask < (1 << n); ++mask) {
            dp[0][mask] = 0;
        }
        for (int i = 1; i <= m; ++i) {
            for (int premask = 0; premask < (1 << n); ++premask) {
                if (dp[i - 1][premask] == -1) continue;
                for (int mask = 0; mask < (1 << n); ++mask) {
                    if ((mask & avail[i]) != mask) continue;
                    if (mask & (mask >> 1)) continue;
                    if ((mask & (premask << 1)) || (mask & (premask >> 1))) continue;
                    dp[i][mask] = max(dp[i][mask], dp[i - 1][premask] + countOnes(mask));                
                }
            }
        }
        for (int mask = 0; mask < (1 << n); ++mask) {
            res = max(res, dp[m][mask]);
        }
        return res;
    }
    int countOnes(int mask) {
        int res = 0;
        while (mask > 0) {
            res += mask & 1;
            mask >>= 1;
        }
        return res;
    }
};

Github 同步地址:

#1349

参考资料：

https://leetcode.com/problems/maximum-students-taking-exam/

https://leetcode.com/problems/maximum-students-taking-exam/solutions/503686/a-simple-tutorial-on-this-bitmasking-problem/

https://leetcode.com/problems/maximum-students-taking-exam/solutions/503763/c-dp-bitmasking-inspired-by-tmwilliamlin168/

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~