EvenPaths
TCO12 Round 2A · 2012-03-27 · by rng_58
TCO12 Round 2A · 2012-03-27 · by rng_58 · Brute Force, Dynamic Programming, Graph Theory, Math
Problem Statement
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 aString[] 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
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.
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
0)
{"NNYYNNNYYN", "NNNNNNNNNN", "NYNNNNNNNY", "NNNNNNNNNN", "NNYNNYYNNN", "NNNNNNNNNN", "NYNYNYNNNY", "NYNNYYNNYN", "NYNYYYYNNY", "NYNYNNNNNN"}
"---?-????-"
Returns: 16
1)
{"NYYY", "NNNN", "NNNY", "NNNN"}
"--??"
Returns: 0
2)
{"NY", "NN"}
"--"
Returns: 0
3)
{"NY","NN"}
"--"
Returns: 0
4)
{"NYNY","NNNN","YYNY","NYNN"}
"--??"
Returns: 2
5)
{"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.
6)
{"NYYNN", "NNNNY", "NYNNN", "YNNNN", "NNNNN"}
"--???"
Returns: 4
The maze is nice if and only if room 2 doesn't contain an obstacle.
7)
{"NNNNN", "NNYYN", "YNNNY", "NNNNN", "NNNNN"}
"--???"
Returns: 8
There is no path from room 0 to room 1 regardless of obstacles.
Submissions are judged against all 105 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EvenPaths with a public method long long theCount(vector<string> maze, string rooms) · 105 test cases · 2 s / 256 MB per case