In a popular game, a ball is dropped from the top of a triangle of cells containing n rows. The
ball keeps falling down row by row until it reaches the bottom of the triangle. In each row, the ball can fall either left or right.
The first row contains one cell, the second contains two, and so on. The game looks like the following picture (where a cell is the space between
two consecutive points in a row):
The rows are numbered from top to bottom starting from zero, and the cells in each row are numbered from left to right
starting from zero. Note that row i will have i+1 cells numbered 0 to i, and if the ball
is on cell k of row i, it will either fall left to cell k of row i+1, or right to cell k+1 of row i+1.
Given a String[] cells, containing a list of cells, and an int n, the number of rows in the triangle,
return the number of paths in which the ball passes through all of the given cells. Each element of cells will be formatted "<row> <cell>" (quotes for clarity), where <row> is the cell's row, and <cell> is the cell's position within that row. |