Hard
题目描述
给你一个 m * n 的矩阵 seats 表示教室中座位的分布。如果座位是坏的（不能坐），就用 '#' 表示；否则，用 '.' 表示。
学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。
学生必须坐在状况良好的座位上。
示例 1：
输入：seats = [["#",".","#","#",".","#"],
[".","#","#","#","#","."],
["#",".","#","#",".","#"]]
输出：4
解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。
示例 2：
输入：seats = [[".","#"],
["#","#"],
["#","."],
["#","#"],
[".","#"]]
输出：3
解释：让所有学生坐在可用的座位上。
示例 3：
输入：seats = [["#",".",".",".","#"],
[".","#",".","#","."],
[".",".","#",".","."],
[".","#",".","#","."],
["#",".",".",".","#"]]
输出：10
解释：让学生坐在第 1、3、5 列的可用座位上。
提示：
seats仅由字符'.'和'#'组成m == seats.lengthn == seats[i].length1 <= m <= 81 <= n <= 8
解题思路
这是一个典型的状态压缩动态规划问题。由于矩阵规模较小（最大8×8），我们可以使用位掩码来表示每一行的学生安排状态。
核心思路：
- 状态表示：用位掩码表示每一行学生的坐法，1表示有学生，0表示没有学生
- 状态转移：
dp[i][mask]表示前i行，第i-1行状态为mask时的最大学生数 - 约束条件：
- 学生只能坐在好座位上（’.’）
- 同一行相邻位置不能都有学生（防止左右作弊）
- 相邻行的斜对角位置不能都有学生（防止左上、右上作弊）
算法步骤：
- 预处理每一行的可用座位掩码
- 枚举每一行所有可能的学生安排
- 检查当前行内部是否合法（无相邻学生）
- 检查与上一行是否冲突（无斜对角学生）
- 状态转移更新最大值
时间复杂度：O(m × 4^n)，其中m是行数，n是列数。每行有2^n种状态，需要与上一行的2^n种状态进行匹配。
空间复杂度：O(2^n)，只需要存储上一行的状态。
代码实现
class Solution {
public:
int maxStudents(vector<vector<char>>& seats) {
int m = seats.size(), n = seats[0].size();
// 预处理每行的可用座位掩码
vector<int> availableSeats(m, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (seats[i][j] == '.') {
availableSeats[i] |= (1 << j);
}
}
}
// 检查掩码是否合法（同一行无相邻学生）
auto isValid = [&](int mask) -> bool {
return (mask & (mask << 1)) == 0;
};
// 检查两行是否冲突（无斜对角学生）
auto noConflict = [&](int mask1, int mask2) -> bool {
return (mask1 & (mask2 << 1)) == 0 && (mask1 & (mask2 >> 1)) == 0;
};
// dp[mask] 表示上一行状态为mask时的最大学生数
vector<int> dp(1 << n, -1);
dp[0] = 0;
for (int i = 0; i < m; i++) {
vector<int> newDp(1 << n, -1);
for (int prevMask = 0; prevMask < (1 << n); prevMask++) {
if (dp[prevMask] == -1) continue;
for (int mask = 0; mask < (1 << n); mask++) {
// 检查当前掩码是否在可用座位范围内
if ((mask & availableSeats[i]) != mask) continue;
// 检查当前行内部是否合法
if (!isValid(mask)) continue;
// 检查与上一行是否冲突
if (!noConflict(mask, prevMask)) continue;
newDp[mask] = max(newDp[mask], dp[prevMask] + __builtin_popcount(mask));
}
}
dp = newDp;
}
return *max_element(dp.begin(), dp.end());
}
};
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
m, n = len(seats), len(seats[0])
# 预处理每行的可用座位掩码
available_seats = []
for i in range(m):
mask = 0
for j in range(n):
if seats[i][j] == '.':
mask |= (1 << j)
available_seats.append(mask)
# 检查掩码是否合法（同一行无相邻学生）
def is_valid(mask):
return (mask & (mask << 1)) == 0
# 检查两行是否冲突（无斜对角学生）
def no_conflict(mask1, mask2):
return (mask1 & (mask2 << 1)) == 0 and (mask1 & (mask2 >> 1)) == 0
# dp[mask] 表示上一行状态为mask时的最大学生数
dp = [-1] * (1 << n)
dp[0] = 0
for i in range(m):
new_dp = [-1] * (1 << n)
for prev_mask in range(1 << n):
if dp[prev_mask] == -1:
continue
for mask in range(1 << n):
# 检查当前掩码是否在可用座位范围内
if (mask & available_seats[i]) != mask:
continue
# 检查当前行内部是否合法
if not is_valid(mask):
continue
# 检查与上一行是否冲突
if not no_conflict(mask, prev_mask):
continue
new_dp[mask] = max(new_dp[mask], dp[prev_mask] + bin(mask).count('1'))
dp = new_dp
return max(dp)
public class Solution {
public int MaxStudents(char[][] seats) {
int m = seats.Length, n = seats[0].Length;
// 预处理每行的可用座位掩码
int[] availableSeats = new int[m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (seats[i][j] == '.') {
availableSeats[i] |= (1 << j);
}
}
}
// 检查掩码是否合法（同一行无相邻学生）
bool IsValid(int mask) {
return (mask & (mask << 1)) == 0;
}
// 检查两行是否冲突（无斜对角学生）
bool NoConflict(int mask1, int mask2) {
return (mask1 & (mask2 << 1)) == 0 && (mask1 & (mask2 >> 1)) == 0;
}
// 计算二进制中1的个数
int PopCount(int x) {
int count = 0;
while (x > 0) {
count += x & 1;
x >>= 1;
}
return count;
}
// dp[mask] 表示上一行状态为mask时的最大学生数
int[] dp = new int[1 << n];
for (int i = 0; i < dp.Length; i++) dp[i] = -1;
dp[0] = 0;
for (int i = 0; i < m; i++) {
int[] newDp = new int[1 << n];
for (int j = 0; j < newDp.Length; j++) newDp[j] = -1;
for (int prevMask = 0; prevMask < (1 << n); prevMask++) {
if (dp[prevMask] == -1) continue;
for (int mask = 0; mask < (1 << n); mask++) {
// 检查当前掩码是否在可用座位范围内
if ((mask & availableSeats[i]) != mask) continue;
// 检查当前行内部是否合法
if (!IsValid(mask)) continue;
// 检查与上一行是否冲突
if (!NoConflict(mask, prevMask)) continue;
newDp[mask] = Math.Max(newDp[mask], dp[prevMask] + PopCount(mask));
}
}
dp = newDp;
}
int result = 0;
for (int i = 0; i < dp.Length; i++) {
result = Math.Max(result, dp[i]);
}
return result;
}
}
var maxStudents = function(seats) {
const m = seats.length;
const n = seats[0].length;
// Get all valid seat masks for each row
const validMasks = [];
for (let i = 0; i < m; i++) {
const masks = [];
for (let mask = 0; mask < (1 << n); mask++) {
let valid = true;
for (let j = 0; j < n; j++) {
if (mask & (1 << j)) {
// Check if seat is available
if (seats[i][j] === '#') {
valid = false;
break;
}
// Check left and right neighbors
if ((j > 0 && (mask & (1 << (j - 1)))) ||
(j < n - 1 && (mask & (1 << (j + 1))))) {
valid = false;
break;
}
}
}
if (valid) masks.push(mask);
}
validMasks.push(masks);
}
// DP with memoization
const memo = new Map();
function dp(row, prevMask) {
if (row === m) return 0;
const key = row * (1 << n) + prevMask;
if (memo.has(key)) return memo.get(key);
let maxCount = 0;
for (const mask of validMasks[row]) {
// Check diagonal conflicts with previous row
let valid = true;
for (let j = 0; j < n; j++) {
if (mask & (1 << j)) {
// Check upper left and upper right
if ((j > 0 && (prevMask & (1 << (j - 1)))) ||
(j < n - 1 && (prevMask & (1 << (j + 1))))) {
valid = false;
break;
}
}
}
if (valid) {
const count = __builtin_popcount(mask) + dp(row + 1, mask);
maxCount = Math.max(maxCount, count);
}
}
memo.set(key, maxCount);
return maxCount;
}
function __builtin_popcount(n) {
let count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
return dp(0, 0);
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(m × 4^n) | m是行数，n是列数，每行需要枚举所有可能的状态组合 |
| 空间复杂度 | O(2^n) | 存储状态数组的空间 |