of the ACM International Collegiate Programming Contest
Problem E Cat and Mouse
In a house with many rooms live a cat and a mouse. The cat and the mouse each have chosen
one room as their “home”. From their “home” they regularly walk through the house. A cat can
274 Cat and Mouse
go from room A to room B if and only if there is a cat door from room A to room B. Cat doors
can only be used in one direction. Similarly a mouse can go from room A to room B if and only
In a house with many rooms live a cat and a mouse. The cat and the mouse each have chosen one room
if there is a mouse door from room A to room B. Also mouse doors can be used in only one
as their “home”. From their “home” they regularly walk through the house. A cat can go from room
direction. Furthermore, cat doors cannot be used by a mouse, and mouse doors cannot be used
A to room B if and only if there is a cat door from room A to room B. Cat doors can only be used in by a cat.
one direction. Similarly a mouse can go from room A to room B if and only if there is a mouse door from room A to room B. Also mouse doors can be used in only one direction. Furthermore, cat doors
Given a map of the house you are asked to write a program that finds out
cannot be used by a mouse, and mouse doors cannot be used by a cat.
Given a map of the house you are asked to write a program that finds out
- if there exist walks for the cat and mouse where they meet each other in some room,
and
- if there exist walks for the cat and mouse where they meet each other in some room, and
- if the mouse can make a walk through at least two rooms, end in its “home” room again, and along the way cannot ever meet the cat. (Here, the mouse may not ever
- if the mouse can make a walk through at least two rooms, end in its “home” room again, and
meet the cat, whatever the cat does.)
along the way cannot ever meet the cat. (Here, the mouse may not ever meet the cat, whatever the cat does.)
CAT
room 3 m room 4
m
MOUSE
m ccmc
m
room 5
mcm room 1 c room 2
m is a mouse door c is a cat door
This picture corresponds to the Sample Input below.
Forexample,iintthheemaapp,,thtehecactactacnanmemeetetthethmeomusoeusienirnoormoosm0s,1,a2n,dan2d.A3l.soA,ltshoe,mthoeumseocuasne can makmeaakewalwkatlhkrothurgohutgwhotwroormosomwisthwoiuthtoeuvteervmereemtienegtitnhgetchaet,cavti,zv.,iza.,roaurnoduntdriptrifprofmromrooromom5 t4ot4oand bac3k.and back.
Input
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases
The input consists of integers and defines the configuration of the house. The first line has
following, each of them as described below. This line is followed by a blank line, and there is also a
three integers separated by blanks: the first integer defines the number of rooms, the second the
blank line between two consecutive inputs.
initial room of the cat (the cat’s “home”), and the third integer defines the initial room of the
The input consists of integers and defines the configuration of the house. The first line has three
mouse (the mouse’s “home”). Next there are zero or more lines, each with two positive inte-
integers separated by blanks: the first integer defines the number of rooms, the second the initial room
gers separated by a blank. These lines are followed by a line with two 1’s separated by a blank.
of the cat (the cat’s “home”), and the third integer defines the initial room of the mouse (the mouse’s
The pairs of positive integers define the cat doors. The pair A B represents the presence of a cat “home”). Next there are zero or more lines, each with two positive integers separated by a blank. These
lines are followed by a line with two ‘-1’s separated by a blank. The pairs of positive integers define the cat doors. The pair A B represents the presence of a cat door from room A to room B. Finally there are zero or more lines, each with two positive integers separated by a blank. These pairs of integers define the mouse doors. Here, the pair A B represents the presence of a mouse door from room A to room B.
274 – Cat and Mouse 2/2 The number of rooms is at least one and at most 100. All rooms are numbered consecutively starting
at 1. You may assume that all positive integers in the input are legal room numbers. Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output consists of two characters separated by a blank and ended by a new-line character. The first character is ‘Y’ if there exist walks for the cat and mouse where they meet each other in some room. Otherwise, it is ‘N’. The second character is ‘Y’ if the mouse can make a walk through at least two rooms, end in its “home” room again, and along the way cannot ever meet the cat. Otherwise, it is ‘N’.
Sample Input
1
535 12 21 31 43 52 -1 -1 13 25 34 41 42 45 54
Sample Output
YY