1377. Maximum Students Taking Exam

A classroom is given as a grid of rows where '.' marks a usable seat and '#' marks a broken one. A student can copy from the seats immediately left, immediately right, upper-left and upper-right of their own. Seat as many students as possible so that no student can copy from another, and return that maximum number.

Input: A JSON object {"seats": [<row strings of '.' and '#'>]}.

Output: Return the maximum number of students that can be seated.

Examples

Input: {"seats":["#.##.#",".####.","#.##.#"]}
Output: 4
Explanation: At most four students can sit without copying.

Input: {"seats":[".##",".##",".##"]}
Output: 3
Explanation: Only the first column is usable, seating three students.

Constraints

• 1 <= rows <= 8
• 1 <= columns <= 8
• each character is '.' or '#'

Asked by