Bus routes
In the newly developed suburb of Mykolaiv, which is laid out in a rectangular grid, all roads run either strictly from south to north or from west to east. This means that any two roads are either parallel or intersect at right angles, forming intersections. The suburb features N horizontal roads and M vertical roads, resulting in a total of N*M intersections.
A bus route network is being designed for the suburb. Each route must begin at the intersection in the bottom left corner of the map and end at the intersection in the top right corner. Additionally, the bus must travel along the shortest possible path, moving only north or east. At any intersection, the bus can change direction from north to east or vice versa. Some intersections are deemed important because they are near densely populated areas, and at least one bus route must pass through each of these important intersections.
Task
Your task is to design the bus routes so that at least one route passes through each important intersection, while minimizing the total number of routes.
Input
The first line of the input file busways.in contains two natural numbers: the number of horizontal roads N and the number of vertical roads M in the suburb. It is given that 2 ≤ N ≤ M ≤ 1000. The next N lines each contain M numbers: a 1 indicates an important intersection, and a 0 indicates a non-important intersection.
Output
The output file busways.out should contain a single non-negative integer, representing the minimum number of routes needed to cover all important intersections while traveling along the shortest paths from the bottom left to the top right intersection.
Scoring
Subtask Points Additional Constraints Required Subtasks
0 0 Tests from the condition -
1 12 N = 2 -
2 18 The number of important intersections does not exceed 3 -
3 22 M ≤ 60 -
4 16 M ≤ 250 0, 3
5 32 No additional constraints 0, 1, 2, 3, 4