Problem Statement |
| |
There is a rectangular table divided into r rows and c columns, for a total of r * c fields.
The rows are numbered 1 to r, from bottom to top, and the columns are numbered 1 to c, from left to right.
All coordinates in this problem will be given as (row, column).
You are given int[]s fieldrow and fieldcol containing a list of special fields in the
table, where (fieldrow[i], fieldcol[i]) are the coordinates of the i-th field. For each number n,
where 0 <= n <= the number of elements in fieldrow, you must count the number of different paths from field (1, 1)
to field (r, c) that contain exactly n special fields. These paths are called paths of length n.
There are two rules you must follow. First, you are only allowed to make moves that are straight up or to the right.
In other words, from each field (row, column), you can only move to field (row+1, column) or field (row, column+1).
Second, in each path, all the special fields must appear in the same order that they appear in the input.
In other words, if the path contains field a = (fieldrow[idxa], fieldcol[idxa]) and
field b = (fieldrow[idxb], fieldcol[idxb]), and a appears before b in the path, then idxa must be less than idxb.
Return a int[] containing exactly k+1 elements, where k is the number of elements in fieldrow.
The i-th element (0-indexed) must be the number of different paths of length i modulo 1000007.
|
| |
Definition |
| | | Class: | CountPaths | | Method: | difPaths | | Parameters: | int, int, int[], int[] | | Returns: | int[] | | Method signature: | int[] difPaths(int r, int c, int[] fieldrow, int[] fieldcol) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | r and c will each be between 1 and 50, inclusive. |
| - | fieldrow will contain between 0 and 50 elements, inclusive. |
| - | fieldcol and fieldrow will contain same number of elements. |
| - | Each element of fieldrow will be between 1 and r, inclusive. |
| - | Each element of fieldcol will be between 1 and c, inclusive. |
| - | For all i and j, where i < j, the pairs (fieldrow[i], fieldcol[i]) and (fieldrow[j], fieldcol[j]) will be different. |
| |
Examples |
| 0) | |
| | | Returns: {1, 3, 2 } | Path of length 0:
(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)
Paths of length 1:
(1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3)
(1, 1) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3)
(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)
Paths of length 2:
(1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3)
(1, 1) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3)
|
|
|
| 1) | |
| | |
| 2) | |
| | | Returns: {42, 14, 10, 4 } | |
|
| 3) | |
| | 35 | 37 | {3, 28, 28, 27, 27, 5, 15, 23, 21, 3, 8, 25, 34, 31, 33, 35, 13, 34} | {12, 34, 3, 9, 34, 3, 18, 17, 26, 5, 23, 14, 20, 7, 3, 20, 19, 23} |
| Returns:
{830519, 709835, 755976, 219563, 868547, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } | |
|
| 4) | |
| | | Returns: {0, 0, 0 } | | There is no path that passes through (50, 50) before (1, 1). |
|
|