给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。
学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。
学生必须坐在状况良好的座位上。
示例 1：
输入：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
2. 结题思路
2.1. 思路过程
- 当前行的状态只和前一行的状态有关。
- 为了表示前一行的状态，加上题目矩阵规模小于8，可以使用状态压缩。
- 一个简便方法，采用位运算快速进行移位，以及有效状态的判断。
2.2. 细节考虑
- 位运算，通过左移，右移一位，可以快速判断，当前的状态是否合法。
- 将合法的座位，映射为0。坏掉的座位，映射为1，与当前状态与（&），可以快速判断当前状态是否合法
3. 代码
public int maxStudents(char[][] seats) {
int m = seats.length;
int n = seats[0].length;
int[][] dp = new int[m + 1][1 << n];
int[] tmp = new int[m];
int sum;
for (int i = 0; i < m; i++) {
sum = 0;
for (char c : seats[i]) {
sum = sum << 1;
if (c == '#') {
sum += 1;
}
}
tmp[i] = sum;
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < 1 << n; j++) {
if ((j & (j << 1)) == 0 && (j & (j >> 1)) == 0 && (j & tmp[i]) == 0) {
for (int k = 0; k < 1 << n; k++) {
if ((k & (j << 1)) == 0 && (k & (j >> 1)) == 0) {
dp[i][j] = Math.max(dp[i][j], Integer.bitCount(j) + dp[i + 1][k]);
}
}
}
}
}
int result = 0;
for (int i = 0; i < 1 << n; i++) {
result = Math.max(0, dp[0][i]);
}
return result;
}
