StringPath
SRM 591 · 2013-06-25 · by gojira_tc
SRM 591 · 2013-06-25 · by gojira_tc · Dynamic Programming
Problem Statement
Problem Statement
Manao has a rectangular board divided into n times m cells.
The rows of the board are numbered from 1 to n and the columns are numbered from 1 to m.
The cell in row i, column j is referred to as (i, j).
Each cell contains an uppercase letter of the English alphabet.
Having such a board, Manao likes to traverse it. The traversal always starts in the cell (1, 1). In each step of the traversal Manao moves either one cell down or one cell to the right. That is, from any cell (x, y) Manao will move either to (x+1, y) or to (x, y+1). The traversal always ends in the cell (n, m). During the traversal Manao records the letters in the visited cells (including the first and the last cell). The obtained string is called a string path for the given board.
You are given theint s n and m, and two distinct String s A and B.
Manao claims that he performed two different traversals of his n x m board and obtained the string paths A and B.
Compute the number of different boards for which this is possible.
Return this number modulo 1,000,000,009.
Having such a board, Manao likes to traverse it. The traversal always starts in the cell (1, 1). In each step of the traversal Manao moves either one cell down or one cell to the right. That is, from any cell (x, y) Manao will move either to (x+1, y) or to (x, y+1). The traversal always ends in the cell (n, m). During the traversal Manao records the letters in the visited cells (including the first and the last cell). The obtained string is called a string path for the given board.
You are given the
Constraints
- n will be between 1 and 8, inclusive.
- m will be between 1 and 8, inclusive.
- A and B will be exactly n+m-1 characters long.
- A and B will consist of uppercase letters ('A'-'Z') only.
- A and B will be distinct.
Examples
0)
2 2 "ABC" "ADC" Returns: 2
The two possible boards are: AB AD DC BC
1)
2 2 "ABC" "ABD" Returns: 0
It is impossible for two string paths to have a different last letter.
2)
3 4 "ABCDDE" "ACCBDE" Returns: 1899302
3)
8 8 "ZZZZZZZZZZZZZZZ" "ZABCDEFGHIJKLMZ" Returns: 120390576
4)
1 1 "A" "B" Returns: 0
Submissions are judged against all 40 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StringPath with a public method int countBoards(int n, int m, string A, string B) · 40 test cases · 2 s / 256 MB per case