Connection Status:
Competition Arena > EvenPaths

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
Class Name: EvenPaths
Return Type: long
Method Name: theCount
Arg Types: (vector<string>, string)
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 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.

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 '-'.

Statement by TopCoder, Inc. — view the original on the archive.

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

Submitting as anonymous