1349. Maximum Students Taking Exam¶
题目信息¶
- 题号:
1349
- 难度:
Hard
- 主题:
状态压缩动态规划、座位安排
- 原题:
- 重点:
只能坐在
.座位;学生不能看到同排左右相邻位置,也不能看到前一排左上或右上位置
题目重述¶
给定教室座位矩阵 seats,. 表示可用座位,# 表示损坏座位。安排学生参加考试,每个学生坐在一个可用座位上。
若另一名学生位于其左侧、右侧、左上或右上相邻位置,则可以作弊,因此这些位置不能同时坐人。请返回最多可安排的学生数量。
1 <= seats.length, seats[i].length <= 8。
自建示例¶
上下正对的座位可以同时使用:
输入:seats = [[".","."],[".","."]]
输出:2
解释:可以选择同一列的上下两个座位;水平相邻和斜对角组合都不合法。
损坏座位可隔开同一排学生:
输入:seats = [[".","#","."]]
输出:2
解释:两个可用座位不相邻,可同时安排学生。