544. How Many Paths Score Best
Walk from the top-left cell to the bottom-right cell, moving only RIGHT or DOWN. Cells
holding -1 are BLOCKED and cannot be entered. A path's score is the total of every cell it
visits, including both ends.
Print the best achievable score and, separated by a space, how many paths achieve it, the
count modulo 1000000007. If no path exists at all, print 0 0.
0 1 2
3 4 5 -> 24 1
6 7 8
## Carrying the count beside the optimum
This is problem #453's recipe on a grid:
val[r][c] = the best score reaching (r, c), or unreachable
cnt[r][c] = how many paths achieve val[r][c]
For each of the two predecessors that is reachable:
strictly better -> val = that; cnt = that predecessor's count REPLACE
equal -> cnt += that predecessor's count ADD
A strict improvement makes every previously counted path irrelevant, so the count is REPLACED. A tie describes disjoint families, since a path arrives from above or from the left and never both, so the counts ADD.
Using += in both cases overcounts and = in both undercounts, and neither produces an
error.
## Unreachable is not zero
A blocked cell is unreachable, and so is any cell whose only predecessors are unreachable. That is different from a cell reachable with score 0.
0 -1
1 1 -> 2 1
The top-right cell is blocked, so the only route is down then right. If unreachable were encoded as score 0 with count 0, the arithmetic still works here by luck; encode it as score 0 with count 1 and the answer gains a phantom path.
Use a sentinel for the score and test it before extending, exactly as in problem 491.
## Blocked endpoints
If the start or the destination is blocked, no path exists and the answer is 0 0. Those
are separate tests, because a solution that only checks one of them passes half of them.
## Counting by path, not by score
5 0 0 / 0 0 0 / 0 0 5 answers 10 6: every one of the six routes collects both fives and
nothing else, so all six tie.
1 0 1 / 0 1 0 / 1 0 1 answers 3 6 for the same reason with a different arrangement. Both
are worth checking by hand once, because a solution that keeps only one optimal path reports
a count of 1 and a correct score.
## Cost
Time O(m n). Space O(n) with two rows.
Constraints - `1 ≤ m ≤ 200` - `1 ≤ n ≤ 200` - each value is `-1` or between `0` and `9`
Input
The first line contains two integers m and n.
Each of the next m lines contains n integers, where -1 means blocked.
Output
Print the best score and how many paths achieve it, separated by a space, the count modulo 1000000007. Print 0 0 if no path exists.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.