P4304 [TJOI2013] Attack Devices

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.

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 a single integer, the maximum number of devices that can be placed so that no two devices attack each other.

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