Mars Rover Path Optimization

The landing module of a Mars expedition has several obstacle‐detecting rovers. When the module lands on the Martian surface, the rovers leave the landing site and proceed toward the remote transmitter. On their way they must collect rock samples. Each rock sample is collected only by the first rover to encounter it, and once collected it is no longer available; however, any rover (even after the rock is collected) may pass through that cell. The rovers cannot go through cells that contain obstacles.

For safety considerations, the rovers are programmed to move only in two directions—south (down) and east (right)—from the landing site to the transmitter. The landing site is located at \((x_1,y_1)\) and the transmitter at \((x_p,y_q)\) in a \(p \times q\) grid. The grid positions are arranged as follows:

[ \begin{bmatrix} (x_1,y_1) & (x_2,y_1) & \dots & (x_{p-1},y_1) & (x_p,y_1) \ (x_1,y_2) & (x_2,y_2) & \dots & (x_{p-1},y_2) & (x_p,y_2) \ \vdots & \vdots & \ddots & \vdots & \vdots \ (x_1,y_q) & (x_2,y_q) & \dots & (x_{p-1},y_q) & (x_p,y_q) \end{bmatrix} ]

If a rover cannot continue moving before reaching the transmitter, then all rock samples it has collected are lost. The mission planners want to design a single movement scheme (i.e. choose one valid route) so that the number of rovers that finally reach the transmitter is maximized (that is, the chosen route must be feasible) and among all such feasible schemes the number of collected rock samples is maximized.

In this problem, you are given the state of each cell in the grid. Your task is to determine, under an optimal movement scheme, whether at least one rover can reach the transmitter, and if so, what is the maximum number of rock samples that can be collected along a valid route from the landing site to the transmitter.

Note: Since the rovers move as a group along the same prescribed route, if the route is valid then exactly one rover reaches the transmitter. Hence, the answer consists of two numbers: the first is either 0 (if no valid route exists) or 1 (if a valid route exists), and the second is the maximum rock sample count along any valid route.

inputFormat

The first line contains two integers p and q (\(1 \leq p,q \leq 1000\)), which represent the number of columns and rows of the grid respectively. Following this are q lines, each containing p space‐separated integers describing the grid row by row (from \(y_1\) to \(y_q\)).

Each integer represents the state of a cell:

• 0: free cell
• 1: cell with a rock sample
• 2: obstacle (impassable cell)

The landing site is at the top‐left cell (corresponding to \((x_1,y_1)\)) and the transmitter is at the bottom‐right cell (corresponding to \((x_p,y_q)\)).

outputFormat

Output two space‐separated integers on a single line. The first integer is 1 if there exists a valid route from the landing site to the transmitter and 0 otherwise. The second integer is the maximum number of rock samples that can be collected along any valid route. (If no valid route exists, output 0 0.)

sample

3 3
0 1 0
0 2 0
0 0 0

1 1