Seat the Most Students Without Cheating
An exam hall is a grid of good and broken seats. A student can copy from the seat directly left, right, and the four diagonal neighbors. Seat as many students as possible so no one can copy.
Problem
Given an m x n grid where '.' is a usable seat and '#' is broken, place students so that no student sits to the immediate left or right of another, nor on either upper-left or upper-right diagonal of another. Return the maximum number of students that can be seated.
Input
An m x n character grid (each cell '.' or '#').
Output
An integer: the maximum number of seated students.
Constraints
- 1 <= m <= 8
- 1 <= n <= 8
- Each cell is '.' (good) or '#' (broken).
Examples
Example 1
Input
seats = [[".","#","."],["#",".","#"],[".","#","."]]
Output
4
The four corners can all be seated without any left/right/diagonal conflict.
Example 2
Input
seats = [[".","."],[".","."]]
Output
2
Seat the two diagonal cells; same-row adjacency and upper diagonals are avoided.