Maximum Non-Attacking Attack Devices Placement in a 01 Matrix

Given an m x n binary matrix where each cell is either '0' or '1', you are allowed to place an attack device in cells that contain '0'. Each attack device placed at coordinates \((x,y)\) can attack exactly eight positions according to the following knight‐move pattern (in chess):

\[ \begin{array}{cccc} & (x-2,y-1) & & (x-2,y+1) \\ (x-1,y-2) & & & (x-1,y+2) \\ & (x+1,y-2) & & (x+1,y+2) \\ & (x+2,y-1) & & (x+2,y+1) \end{array} \]

Your task is to determine the maximum number of attack devices you can place on the grid such that no two devices attack each other.

inputFormat

The first line contains two integers \(m\) and \(n\) denoting the number of rows and columns respectively. The following \(m\) lines each contain a string of length \(n\) consisting only of characters '0' and '1', representing the grid.

outputFormat

Output a single integer — the maximum number of attack devices that can be placed on the grid without any two devices attacking each other.

sample

2 2
00
00

4