You are a technician for the Air Conditioning Machinery company (ACM). Unfortunately, when you arrive at a customer site to install some air conditioning ducts, you discover that you are running low on supplies. You have only six duct segments, and they are all of the same kind, called an “elbow.”
You must install a duct in a confined space: a rectangular prism whose sides are multiples of a unit length. Think of the confined space as consisting of an array of unit cubes. Each elbow occupies exactly four unit cubes, as shown in Figure 1 below. A unit cube can be occupied by at most one elbow. Each elbow has exactly two openings, as indicated by the gray squares in the elbow shown in Figure 1. You may assemble the elbows into longer ducts, but your duct must be completely contained inside the given space. One way to connect two elbows is shown in Figure 2. Your task is to connect an inflow to an outflow. The inflow and the outflow are located on the exterior surface of the confined space, aligned with the unit cubes, as shown in Figure 3. To keep expenses down, you must accomplish this task while using the minimum number of elbows.
Input
The input consists of several test cases, each of which consists of a single line containing eleven input values separated by blanks. The input values for each test case are as follows.
The first three input values are integers (xBmaxB, yBmaxB, and zBmaxB) that indicate the size of the confined space in the x, y, and z dimensions, respectively. Each unit cube in the confined space can be identified by coordinates (x, y, z) where 1 ≤ x ≤ xBmaxB, 1 ≤ y ≤ yBmaxB, and 1 ≤ z ≤ zBmaxB. xBmaxB, yBmaxB, and zBmaxB are all positive and not greater than 20.
The next three input values are integers that indicate the location of the inflow by identifying the x, y, and z coordinates of the unit cube that connects to the inflow.
The next input value is a two-character string that indicates the direction of the inward flow, using one of the following codes: +x, -x, +y, -y, +z, -z. The inflow connection is on the face of the unit cube that receives this inward flow. For example, if the data specifies an inflow direction of +y, the inflow connection is on the face of the unit cube that faces in the negative y direction. The next three input values are integers that indicate the location of the outflow by identifying the x, y, and z coordinates of the unit cube that connects to the outflow.
The last input value is a two-character string that indicates the direction of the outward flow, using the same codes described above. The outflow connection is on the face of the unit cube that generates this outward flow. For example, if the data specifies an outflow direction of +y, the outflow connection is on the face of the unit cube that faces in the positive y direction.
The last line of the input file consists of a single zero to indicate end of input.
Output
For each test case, print the case number (starting with 1) followed by the minimum number of elbows that are required to connect the inflow to the outflow without going outside the confined space. If the task cannot be accomplished with your supply of six elbow segments, print the word TImpossibleT instead. Use the format in the sample data.
Sample Input
5 4 3 3 1 1 +z 5 4 3 +x
5 4 3 3 1 1 +z 1 2 3 -x
0
Output for the Sample InputCase 1: 2
Case 2: Impossible
题意很简单：用不超过6块上述形状的管道（暂且称为管道吧），问最少需要几块能将出口和入口连通。如果不能，输出"Impossible"。这题类似于三维的迷宫问题，对于每个状态，可以有8种不同的操作，每增加一个操作，对应于多用了一块管道。有所不同的是：每个状态除了它的坐标(x,y,z)外，还多了一个方向向量V∈{+x,+y,+z,-x,-y,-z}。将这个因素也考虑到状态判重里，然后用dfs或者bfs都可解决。还有一个需要注意的是，在进行第一步操作的时候，要根据入口的方向V，对3个坐标x,y,z其中的一个进行+1或者-1操作，由向量V决定。至于为什么，仔细观察下图就明白了。