题目描述

Like most engineering students, Jason relies on caffeine, soda in particular, to get him through long nights in the lab. He’s not too picky about the brand; as long as it’s fizzy, loaded with caffeine, and not the “diet” version, he’s happy. When the new Harris Engineering Center opened on the UCF Campus, he was pleased to see a soda machine on every floor. Not just any soda machine, either. These machines are the fancy kind that display all of the soda stock arranged in rows stacked on top of each other (like most snack machines). When a soda is purchased, a conveyor belt rises to the correct row, where the soda is surgically picked up by a robotic clasp that can travel left and right on the conveyor. The conveyor then descends to the vending slot, where the clasp gently deposits the soda. Finally, the slot unlocks and tilts forward, allowing the buyer to retrieve his or her soda. Engineering perfection! And as a bonus, the soda isn’t subjected to all the usual mechanical clatter that causes it to fizz over when it’s opened.

Unfortunately, these elaborate machines seem to have a propensity for component failure. On one soda mission from his lab, Jason discovered that the vending slot was broken on the machine on his floor, which prevented it from working altogether. He went to the next floor down and saw that that machine’s vending slot was fine, but the conveyor was broken. He went down to the ground floor and saw that that machine was in perfect order, but only had caffeine free diet soda! At this point, Jason devised a plan. It’s a simple matter for him to open up the working machine and harvest the parts he needs for the machine upstairs, then to hike back upstairs and repair the machine that houses the soda he needs. Sure, hecouldjust take the soda he wants while the machine is open, but what fun would that be?

The one issue with this plan is that while Jason does enjoy the engineering challenge, he hates the walking between various broken machines each time he goes to get a coke, so he’s asked you, a computer science student and fellow resident of the Harris Engineering Center to help. He can devise a way to monitor each machine in the building and ascertain what parts are working. He needs you to write a program that will allow him to get all the parts he needs from the various machines in the building, traveling up and down as few flights of stairs as possible (he doesn’t trust the elevators because he’s never been allowed to see how they work). Assume he can carry an unlimited number of parts. He also wants this algorithm to work for various kinds of coke machines and various buildings, in case the vendors decide to change out their machines one day, or the administration decides to relocate the EECS department again (you still can assume that there will always be exactly one coke machine on each floor).

The Problem:

Given the number of floors in the building, the number of parts required for a working machine, a description of the working parts in each machine in the building, and whether or not each machine has the desired kind of soda, determine the smallest number of floor changes required to

assemble a working machine that is already stocked with the desired soda. Jason will always start from his lab and return there after getting his soda.

输入格式

There will be multiple sodamachine arrangements to process. Inputwill begin with three integers,N,F, andP(1 ≤N,F,P≤ 10), each separated by a singlespace with no leading or trailingspaces.Ndescribes the number of floors in the building,Findicates which floor Jason’s lab is on, andPindicates the number of different partsin each of the building’s soda machines.

On the nextNlines will be a set of integersfollowed by a single letter. Eachline describes the soda machine onone floor (starting with the ground floor, and proceeding upward in order). The characterson a line are separated by a single space, with no leading or trailing spaces.The first integers on each line will beS(0 ≤S≤P), indicating the number of workingparts in the machine.Sintegerswill follow, each indicating a working part in the machine (each of these integers will be unique and will bebetween 1 andP). Finally, there willbe a single character “Y” or “N”, where “Y” indicates that themachine has a kind of soda that Jason likes, and “N” indicates that it does not.

End of input will beindicated by a value of 0forN,F, andP. This case should not be processed.

输出格式

For each soda machinearrangement, print the case number (starting with 1) and a single integer indicating the minimum number of timesJason will have to travel up or down a staircase to collect the parts he needs to repair a soda machine, get a sodathat he wants, and return to his lab. Ifthere is no way for Jason to get a soda, print “Impossible” instead of the integer. Leavea blank line after the outputfor each test case.

样例

4 2 5
5 1 2 3 4 5 N
4 1 2 3 5 Y
4 1 2 4 5 Y
5 1 2 3 4 5 Y
4 2 6
1 1 Y
2 2 3 Y
3 1 4 5 Y
0 Y
0 0 0

Test case #1: 2

Test case #2: Impossible