Exam Seating Without Peeking

Hard

A lecture hall is described by hall, a grid of m rows with n seats each. '.' is a working seat and '#' is a broken one that cannot be used. Row 0 is the one nearest the board. A student can see the papers of whoever sits right next to them on the left or right in the same row, and of whoever sits diagonally in front of them, front-left or front-right. They cannot see the paper of the student directly in front or directly behind. Return the largest number of students that can be seated so that nobody can copy from anybody.

Example 1

hall=[['.', '.', '.'], ['.', '#', '.']] → 4

Seat students at places 0 and 2 in the first row and at 0 and 2 in the second. Sitting directly behind someone is fine, and nobody is side by side or diagonal: 4 students.

Example 2

hall=[['.', '.'], ['.', '.']] → 2

Each row fits only one student (side neighbours could peek), and the two sit in the same column: 2.

Constraints

1 ≤ m ≤ 8
1 ≤ n ≤ 8
each cell hall[i][j] is '.' or '#'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Dynamic Programming Bitmask Matrix

Similar problems

Wire Two Panels Hard One Pick per Shelf Hard Settle Up in the Fewest Transfers Hard Two Groups With the Same Average Hard Assembling Fragments Hard

Input

hall=[['.', '.', '.'], ['.', '#', '.']]

Expected

Run checks the first 3 tests in your browser. Submit checks all 67 tests on the server, hidden ones included.