Problem Description

Given a 0-1 matrix, you can place an attack device on any cell with value 0. Each device at $(x,y)$ can attack in a knight’s move the following 8 positions: $(x-1,y-2)$, $(x-2,y-1)$, $(x+1,y-2)$, $(x+2,y-1)$, $(x-1,y+2)$, $(x-2,y+1)$, $(x+1,y+2)$, $(x+2,y+1)$. Find the maximum number of devices that can be placed so that no two devices attack each other.

Input Format

The first line contains an integer $N$, meaning the matrix size is $N \times N$.
The next $N$ lines each contain a binary string of length $N$, representing the matrix.

Output Format

Output a single integer, the maximum number of devices that can be placed so that no two devices attack each other.

3
010
000
100

4

Hint

For $30\%$ of the testdata, it is guaranteed that $N \le 50$.
For $100\%$ of the testdata, it is guaranteed that $N \le 200$.

Translated by ChatGPT 5