Problem Statement
Cucumberman built a maze. The maze consists of rooms and one-directional corridors. Each corridor leads from one room to another. Rooms are numbered 0 through N-1, where N is the number of rooms. The maze has a special property: for each room X, once you leave room X (by using one of the corridors), you will never be able to get back to room X.
The layout of the maze is described by a String[] maze. The j-th character of the i-th element of maze will be 'Y' if there is a one-directional corridor from room i to room j, and it will be 'N' otherwise. You are also given a String rooms. Some rooms may contain an obstacle. A room with an obstacle cannot be entered. If the i-th character of rooms is '?', room i may contain an obstacle. If it is '-', room i doesn't contain an obstacle.
Cucumberman is interested in the number of paths from room 0 to room 1 (see Notes for a formal definition). If the number of different paths is even, he calls the maze nice. There are 2^K possible states of the maze, where K is the number of '?'s in rooms. Out of these 2^K mazes, some are nice. Find and return their count.
The layout of the maze is described by a String[] maze. The j-th character of the i-th element of maze will be 'Y' if there is a one-directional corridor from room i to room j, and it will be 'N' otherwise. You are also given a String rooms. Some rooms may contain an obstacle. A room with an obstacle cannot be entered. If the i-th character of rooms is '?', room i may contain an obstacle. If it is '-', room i doesn't contain an obstacle.
Cucumberman is interested in the number of paths from room 0 to room 1 (see Notes for a formal definition). If the number of different paths is even, he calls the maze nice. There are 2^K possible states of the maze, where K is the number of '?'s in rooms. Out of these 2^K mazes, some are nice. Find and return their count.
Definition
- Class:
- EvenPaths
- Method:
- theCount
- Parameters:
- String[], String
- Returns:
- long
- Method signature:
- long theCount(String[] maze, String rooms)
- (be sure your method is public)
Notes
- A path from room 0 to room 1 is a sequence of rooms that satisfies the following conditions:1) The first element of the sequence is room 0 and the last element of the sequence is room 1.2) For each element of the sequence (except for the last element), there is a one-directional corridor to the next element.3) No room in the sequence contains an obstacle.
Constraints
- maze will contain between 2 and 50 elements, inclusive.
- Each element of maze will contain N characters, where N is the number of elements of maze.
- Each character in maze will be 'Y' or 'N'.
- maze will satisfy the property from the problem statement. I.e., there is no sequence of corridors that leads from some room X back to the same room X.
- maze will contain at most 500 'Y'.
- rooms will contain N characters.
- Each character in rooms will be '-' or '?'.
- The number of '?' in rooms will be between 0 and 32, inclusive.
- The first two characters of rooms will be '-'.
Examples
{"NYY", "NNN", "NYN"}"--?"
Returns: 1
If room 2 contains an obstacle, there is one path from room 0 to room 1: 0 -> 1. This is not a nice maze. If room 2 doesn't contain an obstacle, there are two paths from room 0 to room 1: 0 -> 1 and 0 -> 2 -> 1. This is a nice maze.{"NYYNN", "NNNNY", "NYNNN", "YNNNN", "NNNNN"}"--???"
Returns: 4
The maze is nice if and only if room 2 doesn't contain an obstacle.{"NNNNN", "NNYYN", "YNNNY", "NNNNN", "NNNNN"}"--???"
Returns: 8
There is no path from room 0 to room 1 regardless of obstacles.{"NNYNYNNY", "NNNNNNNN", "NNNNNYYY", "NYNNNNNN", "NNNNNNNN", "NYNYNNNN", "NYNNYNNN", "NNNYYNYN"}"----???-"
Returns: 4
{"NYNNNNYYYYYYYNYNYNNN", "NNNNNNNNNNNNNNNNNNNN", "NNNNYNYYNYNNNNYNYNYN", "NNNNNNNNNNNNNNNNYYNN", "NNNYNNNNNNYYNNYYNNNY", "NYNNYNYYYYNYNYNYYYNN", "NNNYYNNNYNYYNNYNYYNY", "NNNYNNYNYNYNYNYYYYYN", "NYNYYNNNNNNYYNNYYNNN", "NNNNNNNNNNYNYNNNYYNN", "NYNNNNNNNNNYNNNNYNNY", "NNNNNNNNNNNNNNNNNNNN", "NNNYNNNNNNNNNNYNNYNN", "NNNYYNYNNYNNNNNYYYNN", "NNNNNNNNNNNNNNNNNYNN", "NYNYNNNNNNNNNNYNNNNN", "NNNNNNNNNNNNNNNNNNNN", "NYNNNNNNNNNNNNNNNNNN", "NYNNNNNNNYNYYNNYYYNN", "NYNNNNNNNNNNYNYNYYNN"}"---??-??--??--?-?---"
Returns: 136
{"NNYNNNNYNYYYNYNNYYNYNNYYNYNNNYYYNNNNYNNNYYNNNNYNNY", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNYNNNNNYNNNYNNYNNYNNYYYNYNYNNYYYNYNYYNYYNNNNYNNN", "NNNNNNNNNYNNNNYNNNNNNNNYNNNNYNNNNNNNNNNYNNNNNNNNYN", "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NYNNYNNNNNNNNNYNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNN", "NNNYYNNYNNYNNYNYNNNYYNYYNNNNYNNNYNNNNNYYNYNYYNNYYN", "NYNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNYN", "NYNYYNNYNYNYNNNNNNNNNNNNNNNNNYNNNNNNNNNYNNNNNYYNNN", "NNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNYNNYN", "NYNNYNNYNYNNNNYNNNNNNYNNNNNNNNNNNNNNNNNNNYNNNNNNNN", "NYNNNNNYNNNNNNNNNNNYNNNYNNNNYNNNNNNNNNNNNNNNNNYNNN", "NYNNNYNYNYNNNNNNNNYYNYYNNNNYNNNNNNYNNYYNNNNNYNYNYN", "NNNNYYNNNNNNNNYNNYNYYYNYNNNNNNNYNNYNNNNNYNNNNNNYNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYN", "NYNYNYNNNYYNNNYNNNNNYYYNYNNNNYNNNNNNNYNYNYNNNYYNYN", "NNNNYYNYYYYYNNYNNYNYYNNNNNYNYYNNYNYNNYYYNYYYNNNNYN", "NNNNNNNNYNNYNNNNNNNNNNNNNNNNYYNNYNYNNNNYNNNNNYNYNN", "NNNYNYNYYYYYNNNNNNNNYNYNYNNNYNYNYNYNNNNNYYYNYNNYYN", "NYNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYN", "NNNYYYNYNYNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNN", "NNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNYN", "NNNNNYNNYYYNNNYNNNNYNNNNNNNNNYNNYNYNNYNYNNNNNNNYNN", "NYNNYNNNNNNNNNYNNNNYNYNNNNNNNNNNNNNNNNNNNYNNNYYNNN", "NNNNNYNYYYNNNNYNNYNNNNNNNNNNNYNYNNNNNNNNNNNNNYYYNN", "NNNNYYNYYYYNYNNNYYNYNYYNNNYYNYNNYNNYNYYNYYNYYNYYNY", "NYNNNNNNNYYNNNNNNNNNNNNYNNNNYYNNNNYNNNYNNYNNNYNNYN", "NNNYNYNYNYNNNNNNNNNYNYYNNNYNNYNYYNNNNNNNYNNNNYNNYN", "NYNNNYNNNYNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNYNNN", "NYNYNNNYNYYNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNYNNNYYNNN", "NYNNNNNNYNNNNYYYNYNYNNNNNNNNYYNNNNNNNNNNNNNNNYYNNN", "NNNYYNNNNNYYNNYNNNNNNYNYNNNNYYNNNNYNNNNYNNNNNNYNNN", "NYNYNYNNNNNYNNNNNNNYNNNNNNNNNNNNNNNNNYYNNYNNNYNNYN", "NYNNNNNNNYYNNNNYYYNNNNYNYNYNYNNYYNNYNYNNNNNNNNNNYN", "NNNNYNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNYNNYN", "NYNYYNNYNYNNNNNYNNNYNYNNYNNNNNNNYNNNNNYNNYNYNNNNNN", "NYNNNNNNYNNNNYYNNNYNNYYNNYYYYYNNNYNNNNNYNYYNNNNNNY", "NYNNNYNNNYYNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNNNNNNYNNN", "NNNNNYNNYYNYNNNNNNNNNYNYNNNNYNNNNNNNNNNNNYNNNNNNNN", "NNNNNYNYNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNYNNNNNNNN", "NNNNYNNNYNNNNNNYNNNYNYNYYNNNNYNNNNNNNNNNNYNNNYYNNN", "NNNNYNNYNYNNNNYNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNYYNYN", "NYNNYYNNYNNNNNNNNNNYYYNNNNNNNNNNNNNNNNNNNNNYNNNNNN", "NNNYYNNYYNNNNNYYNNNYNNNNYNYNNNNNNNNNNNNYNNNNNYNNNN", "NNNNNYNYYNYNNNNNYNNYYYYNYNYYYYYNYNYYNNNNYNNNNYYYYN", "NNNNNNNYNNNNNNYNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNYN", "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYN", "NNNYYNNNYYNYNNNNNNNNNYNNNNNNYNNNNNYNNNNNNYNNNNYNNN", "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NYNNNNYYYNYYYYNYNNNNNNNNNNNYNYNNNNNNNNNYNYNYNNNNYN"}"---??--??-????-??????--?????-?-?-??--?-??--??????-"
Returns: 2165839872
Back to all problems