Maximizing T‐Shaped Moves in a 0–1 Matrix

In this problem, you are given an \(n \times n\) matrix \(A\) consisting of 0's and 1's. A move is defined as selecting a T-shaped region in the matrix which contains at least one 1; after selecting the region, all numbers inside that region are set to 0.

The T‐shaped regions are formed by 4 cells. One of the T shapes is defined by the cells \[ (x-1, y),\quad (x, y),\quad (x+1, y),\quad (x, y+1), \] with the rotated versions by 90°, 180° and 270° also considered valid. In other words, the four orientations are defined by the following sets of relative coordinates with respect to a pivot cell \((x,y)\):

• Orientation 0: \((-1,0),\ (0,0),\ (1,0),\ (0,1)\)
• Orientation 1: \((0,-1),\ (0,0),\ (0,1),\ (1,0)\)
• Orientation 2: \((-1,0),\ (0,0),\ (1,0),\ (0,-1)\)
• Orientation 3: \((0,-1),\ (0,0),\ (0,1),\ (-1,0)\)

Your task is to compute the maximum number of moves that can be performed. Note that moves can be performed in any order. In each move the chosen T‐shaped region must contain at least one 1 at the time of selection, and after the move, all four cells in that region become 0. Consequently, if several 1's exist in the region, they will be cleared together. In order to maximize the move count, you need to try to "remove" the 1's one by one if possible.

Note: It is allowed that different moves' regions overlap. The challenge is to choose an order of moves such that each move is valid and the total number of moves is maximized.

inputFormat

The first line contains an integer \(n\) (\(n \ge 3\)). The next \(n\) lines each contain a string of length \(n\) consisting of characters '0' and '1', representing the rows of the matrix.

outputFormat

Output a single integer: the maximum number of moves that can be performed.

sample

3
010
111
000

2