Robot and Candies solution codeforces
Polycarp has a rectangular field ofcells (the size of the field does not exceed cells, ), in each cell of which there can be candy. There are rows and columns in the field.
Let’s denote a cell with coordinatesvertically and horizontally by . Then the top-left cell will be denoted as , and the bottom-right cell will be denoted as .
If there is candy in the cell, then the cell is marked with the symbol ‘1‘, otherwise — with the symbol ‘0‘. Robot and Candies solution codeforces
Polycarp made a Robot that can collect candy. The Robot can move fromeither to , or to . 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.
The first line of input data contains an integer( ) — 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 1‘ corresponds to a cell with candy, the symbol ‘0‘ — an empty cell.and ( , ) — field sizes. This is followed by lines, -th of which describes the -th line of the field. Each of them is a string of size characters: the symbol ‘
It is guaranteed that the sum ofvalues for all input data sets in the test does not exceed .
4 2 2 00 00 3 3 100 000 101 4 5 01000 00001 00010 10000 3 3 111 111 111
Robot and Candies solution codeforces output
0 2 2 4
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 celland collects candies at the positions and . The second time Polycarp can again put the Robot in , and then the Robot will move first to , then to and collect the last candy.
In the fourth set, you can show that the Robot cannot collect all the candies in three passes.