1349.参加考试的最大学生数

链接：1349.参加考试的最大学生数
难度：Hard
标签：位运算、数组、动态规划、状态压缩、矩阵
简介：请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。

题解 1 - rust

• 编辑时间：2023-12-26
• 执行用时：4ms
• 内存消耗：2.05MB
• 编程语言：rust
• 解法介绍：状态压缩，动态规划每一层的所有状态。

use std::collections::HashMap;
fn is1(num: usize, offset: usize) -> bool {
    return (num & (1 << offset)) != 0;
}
fn check1(seats: &Vec<Vec<char>>, row: usize, used: usize) -> bool {
    let mut prev = false;
    for col in 0..seats[0].len() {
        if is1(used, col) {
            if prev || seats[row][col] == '#' {
                return false;
            }
            prev = true;
        } else {
            prev = false;
        }
    }
    true
}
fn check2(seats: &Vec<Vec<char>>, used: usize, pre_used: usize) -> bool {
    for col in 0..seats[0].len() {
        if is1(used, col)
            && (col - 1 >= 0 && is1(pre_used, col - 1)
                || col + 1 < seats[0].len() && is1(pre_used, col + 1))
        {
            return false;
        }
    }
    true
}
fn dfs(
    seats: &Vec<Vec<char>>,
    cache: &mut HashMap<usize, HashMap<usize, i32>>,
    pre_used: usize,
    row: usize,
) -> i32 {
    if row < seats.len() {
        if let Some(Some(res)) = cache.get(&row).map(|item| item.get(&pre_used)) {
            *res
        } else {
            let res = (0..(1 << seats[0].len()))
                .map(|used| {
                    if check1(seats, row, used) && check2(seats, used, pre_used) {
                        used.count_ones() as i32 + dfs(seats, cache, used, row + 1)
                    } else {
                        0
                    }
                })
                .max()
                .unwrap();
            cache.entry(row).or_default().entry(pre_used).or_insert(res);
            res
        }
    } else {
        0
    }
}
impl Solution {
    pub fn max_students(seats: Vec<Vec<char>>) -> i32 {
        let mut cache = HashMap::new();
        (0..(1 << seats[0].len()))
            .map(|used| {
                if check1(&seats, 0, used) {
                    used.count_ones() as i32 + dfs(&seats, &mut cache, used, 1)
                } else {
                    0
                }
            })
            .max()
            .unwrap()
    }
}