1349. Maximum Students Taking Exam

题目信息

题号:

1349

难度:

Hard

主题:

状态压缩动态规划、座位安排

原题:

LeetCode 1349

重点:

只能坐在 . 座位;学生不能看到同排左右相邻位置,也不能看到前一排左上或右上位置

题目重述

给定教室座位矩阵 seats,. 表示可用座位,# 表示损坏座位。安排学生参加考试,每个学生坐在一个可用座位上。

若另一名学生位于其左侧、右侧、左上或右上相邻位置,则可以作弊,因此这些位置不能同时坐人。请返回最多可安排的学生数量。

1 <= seats.length, seats[i].length <= 8。

自建示例

上下正对的座位可以同时使用:

输入:seats = [[".","."],[".","."]]
输出:2
解释:可以选择同一列的上下两个座位;水平相邻和斜对角组合都不合法。

损坏座位可隔开同一排学生:

输入:seats = [[".","#","."]]
输出:2
解释:两个可用座位不相邻,可同时安排学生。