Robot and Candies
Contest: Codeforces Round 756 (Div. 3)
Difficulty rating: 2500
Tags: data structures, graph matchings, greedy

Polycarp has a rectangular field of $$$n \times m$$$ cells (the size of the $$$n \cdot m$$$ field does not exceed $$$10^6$$$ cells, $$$m \ge 2$$$), in each cell of which there can be candy. There are $$$n$$$ rows and $$$m$$$ columns in the field.

Let's denote a cell with coordinates $$$x$$$ vertically and $$$y$$$ horizontally by $$$(x, y)$$$. Then the top-left cell will be denoted as $$$(1, 1)$$$, and the bottom-right cell will be denoted as $$$(n, m)$$$.

If there is candy in the cell, then the cell is marked with the symbol '1', otherwise — with the symbol '0'.

Polycarp made a Robot that can collect candy. The Robot can move from $$$(x, y)$$$ either to $$$(x+1, y+1)$$$, or to $$$(x+1, y-1)$$$. If the Robot is in a cell that contains candy, it takes it.

While there is at least one candy on the field, the following procedure is executed:

- Polycarp puts the Robot in an arbitrary cell on the topmost row of the field. He himself chooses in which cell to place the Robot. It is allowed to put the Robot in the same cell multiple times.
- The Robot moves across the field and collects candies. He controls the Robot.
- When the Robot leaves the field, Polycarp takes it. If there are still candies left, Polycarp repeats the procedure.

Find the minimum number of times Polycarp needs to put the Robot on the topmost row of the field in order to collect all the candies. It is guaranteed that Polycarp can always collect all the candies.

Input format:
The first line of input data contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of input data sets in the test.

Before each input data, there is a blank line in the test. Next is a line that contains integers $$$n$$$ and $$$m$$$ ($$$2 \le m$$$, $$$2 \le n \cdot m \le 10^6$$$) — field sizes. This is followed by $$$n$$$ lines, $$$i$$$-th of which describes the $$$i$$$-th line of the field. Each of them is a string of size $$$m$$$ characters: the symbol '1' corresponds to a cell with candy, the symbol '0' — an empty cell.

It is guaranteed that the sum of $$$n \cdot m$$$ values for all input data sets in the test does not exceed $$$10^6$$$.

Output format:
Print $$$t$$$ lines, each line should contain the answer to the corresponding set of input data: the minimum number of times Polycarpus needs to put the Robot on the topmost row of the field in order to collect all the candies.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first set Polycarp may not put the Robot on the field at all, so the answer "0"

In the second set, Polycarp will need to place the robot on the field twice. The Robot can collect candies like this: for the first time Polycarp puts the Robot in the cell $$$(1, 1)$$$ and collects candies at the positions $$$(1, 1)$$$ and $$$(3, 3)$$$. The second time Polycarp can again put the Robot in $$$(1, 1)$$$, and then the Robot will move first to $$$(2,2)$$$, then to $$$(3, 1)$$$ and collect the last candy.

In the fourth set, you can show that the Robot cannot collect all the candies in three passes.

Example input:
4

2 2
00
00

3 3
100
000
101

4 5
01000
00001
00010
10000

3 3
111
111
111

Example output:
0
2
2
4

Editorial:
Note first that we can solve the two subtasks independently if we consider the coloring as on a chessboard, since at any move of the robot the parity of $$$x + y$$$ does not change.
Now replace the moves $$$(x+1, y-1)$$$, $$$(x+1, y+1)$$$ with moves $$$(x+1, y)$$$, $$$(x+1, y+1)$$$ respectively. This can be done because we simply shifted the rows by some value, with the Robot walking on the same cells it walked on in the original board.
Let's look at the even numbered (gray) cells:
Then we'll go through the columns from left to right, keeping the minimum(by size) set of cells the Robot should be in. Then the transition to the next column will be as follows. Go through the cells from bottom to top, which contain the candy. For each cell, find the closest cell of our set (find the Robot) that is above the current cell. Then we change the square from the set to the current square. If there is no robot for the square in the array, then we need to increase the answer by $$$1$$$ and add the robot to our current square (you can think of it as adding the robot to the very top square in the column and getting all the candies that were above).
In the picture, the red circles indicate the cells where we will put the robot as needed. The pink cells mean that this cell is contained in the set.
The final asymptotic depends on the implementation (you can use a set as data structure, or you can use a vector with two pointers): $$$O(n*m*log(n))$$$ and $$$O(n*m)$$$, respectively.