ScotlandYard

TCO13 Round 2B · 2013-02-19 · by rng_58

TCO13 Round 2B · 2013-02-19 · by rng_58 · Graph Theory

Show categories

Class Name: ScotlandYard

Return Type: int

Method Name: maxMoves

Arg Types: (vector<string>, vector<string>, vector<string>)

Problem Statement

Fox Ciel and Fox Jiro play a game called Scotland Yard. Their version of the game is a bit simplified, so if you know the original game, make sure you read the problem statement carefully.

In the game Ciel and Jiro play, they use a map containing n cities. The cities are numbered 0 through n-1. The map also contains a bunch of arrows. Each arrow leads from one city to another (different) city, and has one of three possible colors. The colors represent three types of transportation: taxis, buses, and metro (subway). Both Ciel and Jiro know all information in this map.

You are given three String[]s: taxi, bus, and metro. The j-th character of the i-th element of taxi is 'Y' if it is possible to travel directly from city i to city j using a taxi, or 'N' if that is not possible. In the same way, bus and metro encode the information about bus and subway travel. Note that all transportation options are one-way. Also note that there are no additional restrictions. (That is, it may be possible to travel between some pairs of cities in both directions, there may be more than one transportation option from city i to city j, and for each transport type there can be arbitrarily many options leaving a given city.)

The game starts by Ciel secretly choosing one of the n cities as her initial location. The game then proceeds in turns. In each turn, first Ciel moves to an adjacent location, then Jiro has the option to announce her new location. More precisely, it looks as follows: Whenever it is Ciel's turn to move, she has to move from her current city X to some other city Y. If there are no transportation options that start in the city X, Ciel announces this and the game ends. Otherwise, she chooses one of the available options and moves to its destination. Additionally, Ciel announces to Jiro the type of the transportation system she used ("taxi", "bus", or "metro"). Whenever it is Jiro's turn, if he is certain of Ciel's current city, he announces it and the game ends. Otherwise, Jiro passes and it's again Ciel's turn to move. (Note that Jiro can use all the information he has: the layout of the map, and the sequence of transportation systems Ciel already announced.)

Ciel's score is the number of travels she made. Return Ciel's score, assuming that she plays optimally. If she can continue the game forever without being discovered by Jiro, return -1 instead.

Notes

The answer will always fit into a signed 32bit integer.

Constraints

taxi will contain between 2 and 50 elements, inclusive.
taxi, bus, and metro will contain the same number of elements.
Each element of taxi, bus, and metro will contain n characters, where n is the number of elements in taxi.
Each character in taxi, bus, and metro will be either 'Y' or 'N'.
The i-th character of the i-th element of taxi, bus, and metro will be 'N'.

Examples

{"NYN",
 "NNY",
 "NNN"}
{"NNN",
 "NNN",
 "NNN"}
{"NNN",
 "NNN",
 "NNN"}
Returns: 2

Ciel starts in city 0. In her first move, she announces "taxi" and moves from 0 to 1. At that moment, Jiro is not certain of her location: she can be in city 1 or in city 2. In her second move, Ciel announces "taxi" and moves from 1 to 2. Jiro announces that Ciel is in city 2 and the game ends.

{"NYY",
 "NNN",
 "NNN"}
{"NNN",
 "NNN",
 "NNN"}
{"NNN",
 "NNN",
 "NNN"}
Returns: 1

After Ciel's first move, Jiro doesn't know her location. Still, the game ends, because Ciel has no more moves.

{"NYYY",
 "YNYY",
 "YYNY",
 "YYYN"}
{"NNNN",
 "NNNN",
 "NNNN",
 "NNNN"}
{"NNNN",
 "NNNN",
 "NNNN",
 "NNNN"}
Returns: -1

Ciel can use taxis to drive back and forth between the cities indefinitely. Jiro has no chance to discover her location.

{"NNY",
 "NNY",
 "NNN"}
{"NYN",
 "NNY",
 "NNN"}
{"NNN",
 "NNN",
 "YNN"}
Returns: 2

Ciel starts by choosing her initial location and the first mode of transport. Here is how Jiro will think after Ciel's first move: Suppose that Ciel announced "taxi". She could have started in city 0 or in city 1, but either way she would take the taxi to city 2. Thus, Jiro knows that Ciel is in city 2 and the game ends. Metro is even simpler. If Ciel announced she took the metro, she must have started in city 2 and then she took the metro to city 0. Jiro announces city 0 and the game ends. If Ciel announed that she took the bus, Jiro is not sure about her location: she can be either in city 1, or in city 2. Regardless of where Ciel started and what she does in the second step after taking a bus in the first step, Jiro will always be able to determine her location and the game ends.

{"NNN",
 "YNY",
 "NNN"}
{"NNN",
 "YNN",
 "YNN"}
{"NNN",
 "NNN",
 "YYN"}
Returns: -1

If Ciel travels back and forth between cities 1 and 2, Jiro will never catch her.

Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ScotlandYard with a public method int maxMoves(vector<string> taxi, vector<string> bus, vector<string> metro) · 123 test cases · 2 s / 256 MB per case