Problem Statement
A man is situated in the left top cell of a labyrinth. The labyrinth looks like a rectangular grid of cells with 8 rows and 8 columns. In a single move, the man can shift to an adjacent cell in one of four directions: left, top, right or bottom. There are walls between some pairs of adjacent cells and the outer border of the labyrinth consists of 32 walls.
The man made a sequence of moves. This sequence is described by the String path, which contains only the letters 'L', 'R', 'U'. and 'D'. If the i-th letter is 'L', then the man moved to the left on his i-th move. 'R' means right, 'U' means up, and 'D' means down. Also, at each cell, he counted the number of walls around him. You are given a String counts, the i-th character of which is the number of walls surrounding the cell he was in before the i-th move. Each character is a digit between '0' and '4', inclusive. The String counts contains one more character than the String path.
Determine the number of different labyrinths that don't conflict with the information in path and counts. Return this number modulo 1000000037.
Definition
- Class:
- GridLabyrinth
- Method:
- howMany
- Parameters:
- String, String
- Returns:
- int
- Method signature:
- int howMany(String path, String counts)
- (be sure your method is public)
Constraints
- path will contain between 0 and 49 characters, inclusive.
- Each letter in path will be 'L', 'R', 'U' or 'D'.
- counts will contain exactly one more character than path.
- Each character in path will be a digit between '0' and '4', inclusive.
- In the given path, the man will never move outside the labyrinth.
- The values in counts that correspond to the same cell will be equal.
Examples
No public sample cases were explicitly marked for this problem in the original data.
Back to all problems