题目描述：
给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。
学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。
学生必须坐在状况良好的座位上。
数据范围：
$1\le m\le 8,1\le n\le 8 $
题解：
对于每一行使用状态压缩，将能放的位置看做 $1$ ，不能放的位置看做 $0$ 。然后可以使用记忆化搜索的做法，枚举第 $index$ 行，枚举第 $index$ 行所有的状态。判断是否是合法状态，判断是否坐到了 $0$ 上，是否左右相邻。
判断坐到了 $0$ 上可以直接 $status | i \neq status$ ，只要出现到 $status$ 中 $0$ 的位置，那么或运算一定不会得到 $status$ 。判断相邻可以使用 $i \wedge (i << 1) \neq 0$ 或者 $i \wedge (i >> 1) \neq 0$ 区别就是一个使用的是右侧的数字，一个使用的是左侧的数字。
然后需要修改下一行的状态，下一行需要排除这一行左上方和右上方的，可以使用 i << 1 | i >> 1 表示左上方和右上方的，然后需要把这些位置为 $0$ ，即取反，然后与运算。
注意第 $0$ 行的下标问题。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<int> s;
vector<vector<int>> dp;
int n, m;
int dfs(int index, int status)
{
if (index < 0)
return 0;
if (dp[index][status] != -1)
return dp[index][status];
int ans = 0;
for (int i = 0; i < (1 << m); ++i)
{
if ((i | status) != status || (i & (i << 1)) != 0)
continue;
int cnt = __builtin_popcount(i);
if (index != 0)
{
int next = s[index - 1] & ~(i << 1 | i >> 1);
ans = max(ans, cnt + dfs(index - 1, next));
}
else
ans = max(ans, cnt);
}
dp[index][status] = ans;
return dp[index][status];
}
int maxStudents(vector<vector<char>> &seats)
{
n = seats.size(), m = seats[0].size();
s.resize(n);
dp.resize(n, vector<int>(1 << m, -1));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (seats[i][j] == '.')
s[i] |= 1 << j;
}
}
return dfs(n - 1, s[n - 1]);
}
};
|