题目

给你一个 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

思路

状态压缩+记忆化搜索+深度优先遍历

解法

class Solution {

    int N, M;
    int[] room;
    int[][] dp;

    public int maxStudents(char[][] seats) {
        N = seats.length; M = seats[0].length; room = new int[N]; dp = new int[1 << M][N + 1];
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                room[i] |= seats[i][j] == '.' ? 0 : (1 << j);
            }
        }
        for (int i = 0; i < (1 << M); i++) {
            Arrays.fill(dp[i], -1);
        }
        return process(0, 0);
    }

    public int process(int pre, int i) {
        if (dp[pre][i] != -1) {
            return dp[pre][i];
        }
        if (i == N) {
            return dp[pre][i] = 0;
        }
        int cur = 0;
        for (int j = 0; j < M; j++) {
            if ((room[i] >> j & 1) == 0 && (pre >> (j - 1) & 1) == 0 && (pre >> (j + 1) & 1) == 0) {
                cur |= 1 << j;
            }
        }
        return dp[pre][i] = dfs(i, cur, 0);
    }

    public int dfs(int i, int cur, int j) {
        if (j == M) {
            return process(cur, i + 1);
        }
        if ((cur >> j & 1) != 0) {
            int ans = dfs(i, cur - (1 << j), j + 1);
            if ((cur >> (j - 1) & 1) == 0) {
                ans = Math.max(ans, 1 + dfs(i, cur, j + 1));
            }
            return ans;
        }
        return dfs(i, cur, j + 1);
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现