1349 Maximum Students Taking Exam 參加考試的最大學生數(shù)

Description:

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:

Example 1:

[圖片上傳失敗...(image-286a0e-1666102627048)]

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 * n 的矩陣 seats 表示教室中的座位分布。如果座位是壞的（不可用），就用 '#' 表示；否則，用 '.' 表示。

學生可以看到左側(cè)、右側(cè)、左上、右上這四個方向上緊鄰他的學生的答卷，但是看不到直接坐在他前面或者后面的學生的答卷。請你計算并返回該考場可以容納的一起參加考試且無法作弊的最大學生人數(shù)。

學生必須坐在狀況良好的座位上。

示例：

示例 1：

[圖片上傳失敗...(image-d6f660-1666102627048)]

輸入：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

思路：

狀態(tài)壓縮 ? 動態(tài)規(guī)劃
設(shè) dp[i][j] 表示前 i 行中第 i 行分布為 j 時的最大學生數(shù), 其中 j 為二進制數(shù), 其位為 1 表示有人, 否則表示沒有人
動態(tài)轉(zhuǎn)移方程為 dp[i][j] = max(dp[i][j], dp[i - 1][k] + num), 其中 num 為該行的人的數(shù)量, 即 j 中 1 的次數(shù)
注意每次都需要檢查位置是否合法
時間復雜度為 O(m * 2 ^ n), 空間復雜度為 O(m * 2 ^ n)

代碼:

C++:

class Solution 
{
public:
    int maxStudents(vector<vector<char>>& seats) 
    {
        int m = seats.size(), n = seats.front().size(), result = 0, pre = 0;
        vector<vector<int>> dp(m + 1, vector<int>(1 << n));
        for (int i = 1; i <= m; i++)
        {
            int cur = 0;
            for (int j = 0; j < n; j++) cur |= ((seats[i - 1][j] == '.') << j);
            for (int j = cur; j > 0; j = (j - 1) & cur)
            {
                if ((!(j & (j >> 1))) and (!(j & (j << 1))))
                {
                    for (int k = 0; k < (1 << n); k++)
                    {
                        if ((!(j & (k >> 1))) and (!(j & (k << 1))))
                        {
                            dp[i][j] = max(dp[i][j], dp[i - 1][k] + __builtin_popcount(j));
                            result = max(result, dp[i][j]);
                        }
                    }
                }
            }
            dp[i].front() = pre;
            pre = result;
        }
        return result;
    }
};

Java:

class Solution {
    public int maxStudents(char[][] seats) {
        int m = seats.length, n = seats[0].length, result = 0, pre = 0, dp[][] = new int[m + 1][1 << n];
        for (int i = 1; i <= m; i++) {
            int cur = 0;
            for (int j = 0; j < n; j++) cur |= ((seats[i - 1][j] == '.' ? 1 : 0) << j);
            for (int j = cur; j > 0; j = (j - 1) & cur) {
                if ((j & (j >> 1)) == 0 && (j & (j << 1)) == 0) {
                    int count = 0, s = j;
                    while (s != 0) {
                        count += ((s & 1) == 1 ? 1 : 0);
                        s >>= 1;
                    }
                    for (int k = 0; k < (1 << n); k++) {
                        if ((j & (k << 1)) == 0 && (j & (k >> 1)) == 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + count);
                            result = Math.max(result, dp[i][j]);
                        }
                    }
                }
            }
            dp[i][0] = pre;
            pre = result;
        }
        return result;
    }
}

Python:

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n, result, pre = len(seats), len(seats[0]), 0, 0
        dp = [[0] * (1 << n) for _ in range(m + 1)]
        for i in range(1, m + 1):
            cur = 0
            for j in range(n):
                cur |= ((seats[i - 1][j] == '.') << j)
            j = cur
            while j:
                if not (j & (j << 1)) and not (j & (j >> 1)):
                    for k in range(1 << n):
                        if not (j & (k << 1)) and not (j & (k >> 1)):
                            dp[i][j] = max(dp[i][j], dp[i - 1][k] + bin(j).count('1'))
                            result = max(result, dp[i][j])
                j = (j - 1) & cur
            dp[i][0] = pre
            pre = result
        return result