题目描述
给你一个 m * n
的矩阵 seats
表示教室中的座位分布。如果座位是坏的(不可用),就用 '#'
表示;否则,用 '.'
表示。
学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷,但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。
学生必须坐在状况良好的座位上。
样例
输入:seats = [["#",".","#","#",".","#"],
[".","#","#","#","#","."],
["#",".","#","#",".","#"]]
输出:4
解释:教师可以让 4 个学生坐在可用的座位上,这样他们就无法在考试中作弊。
输入:seats = [[".","#"],
["#","#"],
["#","."],
["#","#"],
[".","#"]]
输出:3
解释:让所有学生坐在可用的座位上。
输入:seats = [["#",".",".",".","#"],
[".","#",".","#","."],
[".",".","#",".","."],
[".","#",".","#","."],
["#",".",".",".","#"]]
输出:10
解释:让学生坐在第 1、3 和 5 列的可用座位上。
限制
seats
只包含字符'.'
和'#'
m == seats.length
n == seats[i].length
1 <= m <= 8
1 <= n <= 8
算法
(状压 DP) $O(m(2^n)^2)$
- 设状态 $f(i, S)$ 表示考虑了前 $i$ 行,其中第 $i$ 行为状态 $S$ 时的最大值。其中 $S$ 为一个二进制的状态表示。
- 假设行数的下标为 $1$ 到 $m$,则初始时 $f(0, 0) = 0$,其余为负无穷。
- 转移时,枚举 $S_1$ 和 $S_2$,判定状态 $S_2$ 存在且 $S_1$ 和 $S_2$ 这两排的方案合法,则转移 $f(i, S_2) = \max (f(i, S_2), f(i - 1, S_1) + c(S_2))$。其中 $c(S)$ 为 $S$ 状态中有多少个 $1$。
- 最终答案为 $\max (f(m, S))$。
时间复杂度
- 状态数共 $O(m2^n)$ 个,转移数共 $O(2^n)$,故时间复杂度为 $O(m(2^n)^2)$。
空间复杂度
- 需要额外 $O(m2^n)$ 的空间存储状态,$c$ 数组需要 $O(2^n)$ 的空间,故总空间复杂度为 $O(m(2^n)^2)$。
参考文献
C++ 代码
class Solution {
public:
bool check(const vector<vector<char>>& seats, int i, int s1, int s2, int n) {
for (int j = 0; j < n; j++)
if (s2 & (1 << j)) {
if (seats[i][j] == '#')
return false;
if (j > 0 && ((s1 & (1 << (j - 1))) || (s2 & (1 << (j - 1)))))
return false;
if (j < n - 1 && ((s1 & (1 << (j + 1))) || (s2 & (1 << (j + 1)))))
return false;
}
return true;
}
int maxStudents(vector<vector<char>>& seats) {
int m = seats.size(), n = seats[0].size();
vector<vector<int>> f(m + 1, vector<int>(1 << n, 0));
vector<int> c(1 << n, 0);
for (int s = 0; s < (1 << n); s++)
for (int j = 0; j < n; j++)
if (s & (1 << j))
c[s]++;
f[0][0] = 0;
for (int i = 1; i <= m; i++)
for (int s1 = 0; s1 < (1 << n); s1++)
for (int s2 = 0; s2 < (1 << n); s2++)
if (check(seats, i - 1, s1, s2, n))
f[i][s2] = max(f[i][s2], f[i - 1][s1] + c[s2]);
int ans = 0;
for (int s = 0; s < (1 << n); s++)
ans = max(ans, f[m][s]);
return ans;
}
};