题目描述

给定一个三维网格空间，尺寸为xmax⁡×ymax⁡×zmax⁡x_{\max} \times y_{\max} \times z_{\max}xmax​×ymax​×zmax​（均不超过202020）。空间内可以放置一种特殊的管道部件 ——肘（elbow\texttt{elbow}elbow）。每个肘恰好占用444个单位立方体，并且恰好有两个开口（入口和出口）。入口和出口的方向互相垂直。你可以将多个肘首尾相连组成更长的管道，连接时前一个肘的出口面必须紧贴后一个肘的入口面，且方向一致。现给定流入位置（单位立方体坐标）及流入方向，流出位置及流出方向，要求用最少数量的肘（不超过666个）构造一条完全位于空间内部的管道，连接流入与流出。若无法用666个以内肘完成，则输出Impossible。

输入格式

每个测试用例包含一行，共111111个输入值，依次为：

• 三个整数xmax⁡,ymax⁡,zmax⁡x_{\max}, y_{\max}, z_{\max}xmax​,ymax​,zmax​，表示空间尺寸；
• 三个整数，表示流入位置的坐标(xi,yi,zi)(x_i, y_i, z_i)(xi​,yi​,zi​)；
• 一个方向字符串（+x、-x、+y、-y、+z、-z），表示流入方向（该方向指向流入立方体的入口面）；
• 三个整数，表示流出位置的坐标(xo,yo,zo)(x_o, y_o, z_o)(xo​,yo​,zo​)；
• 一个方向字符串，表示流出方向（该方向从流出立方体的出口面离开）。

输入以单独一个0结束。

输出格式

对于每个测试用例，输出Case k:后接最小肘段数，若不可能则输出Impossible。

样例

输入

5 4 3 3 1 1 +z 5 4 3 +x 5 4 3 3 1 1 +z 1 2 3 -x 0

输出

Case 1: 2 Case 2: Impossible

题目分析

本题的核心是：在三维网格中，用若干相同的肘部件拼接一条从流入到流出的路径，使路径完全位于空间内部，且肘的数量最少。

一个肘占用444个连续的单位立方体，其内部路径从入口立方体开始，经过333步到达出口立方体。由于肘的两个开口方向互相垂直，因此这333步的方向序列必须满足特定的几何约束。根据题目描述及图例（未给出），肘的形状可能存在两种基本模式：

• 模式A\texttt{A}A：前两步沿入口方向直走，第三步转向与之垂直的方向；
• 模式B\texttt{B}B：第一步沿入口方向，第二步转向垂直方向，第三步继续沿该垂直方向直走。

这两种模式都保证入口方向与出口方向垂直。每个肘的出口方向就是最后一步的方向。

多个肘连接时，前一个肘的出口立方体与后一个肘的入口立方体相邻，且前一个肘的出口方向恰好等于后一个肘的入口方向（即流体从前者流出，直接进入后者）。

由于最多只能使用666个肘，而空间最大尺寸为202020，我们可以采用深度优先搜索（DFS\texttt{DFS}DFS）暴力枚举所有可能的肘放置方式。对于每个肘，枚举其内部方向序列，并检查路径是否超出空间、是否与其他肘重叠。搜索过程中逐段构建，一旦找到合法路径，则该段数即为最小段数（因为从111开始递增尝试）。

解题思路

状态定义

在DFS\texttt{DFS}DFS中，我们维护以下状态：

• 当前所在单位立方体的坐标(x,y,z)(x, y, z)(x,y,z)；
• 正在构建的肘的索引segIdx（从000开始），以及在该肘内部已走的步数segStep（0∼30 \sim 30∼3，0表示刚进入该肘的入口立方体，3表示已走完三步，位于出口立方体）；
• 该肘的入口方向inDir；
• 当前选择的模式mode（0表示尚未确定，1表示模式A\texttt{A}A，2表示模式B\texttt{B}B）；
• 该肘的出口方向outDir（仅在模式B\texttt{B}B或步数足够时确定）。

转移规则

每一步枚举下一个移动方向ddd，根据当前segStep和mode判断是否合法：

• segStep == 0：第一步必须等于入口方向inDir；
• segStep == 1：
  • 若选择d == inDir，则进入模式A\texttt{A}A（mode = 1），出口方向暂未确定；
  • 若选择d垂直于inDir，则进入模式B\texttt{B}B（mode = 2），并立即确定出口方向outDir = d；
• segStep == 2：
  • 若为模式A\texttt{A}A，则第三步必须垂直于inDir且不等于inDir，此时出口方向即为该方向；
  • 若为模式B\texttt{B}B，则第三步必须等于之前确定的outDir。

当segStep == 3时，该肘构建完毕。此时若还有后续肘，则需要走一个连接步：沿当前出口方向outDir移动一格，到达下一个肘的入口立方体，并将下一个肘的入口方向设为该方向。若当前已经是最后一个肘，则检查当前位置和方向是否与给定的流出位置和方向完全一致。

搜索顺序

因为肘数上限为666，我们依次尝试K=1,2,…,6K = 1, 2, \dots, 6K=1,2,…,6，一旦某个KKK搜索成功，即输出KKK。若所有KKK均失败，则输出Impossible。

剪枝与访问标记

每个单位立方体最多被一个肘占用，因此使用三维布尔数组vis[21][21][21]标记已占用的立方体。搜索时，若下一步到达的立方体超出边界或已被占用，则剪枝。

复杂度分析

• 每个肘内部最多枚举6×6×6=2166 \times 6 \times 6 = 2166×6×6=216种方向组合（实际受垂直约束限制，分支远小于此）；
• 总段数K≤6K \le 6K≤6，总步数最多3K+(K−1)≤173K + (K-1) \le 173K+(K−1)≤17步；
• 空间体积最多203=800020^3 = 8000203=8000，访问标记开销可忽略；
• 实际运行中，由于剪枝非常有效，可在极短时间内完成搜索。

代码实现

// Air Conditioning Machinery// UVa ID: 1068// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 方向映射：0:+x, 1:-x, 2:+y, 3:-y, 4:+z, 5:-zintdx[6]={1,-1,0,0,0,0};intdy[6]={0,0,1,-1,0,0};intdz[6]={0,0,0,0,1,-1};intX,Y,Z;// 空间尺寸intsx,sy,sz,ex,ey,ez;// 入口/出口立方体坐标intsinDir,soutDir;// 入口/出口方向intK;// 当前尝试的肘段数boolvis[21][21][21];// 访问标记，最大20// 判断两个方向是否垂直（点积为0）boolisVertical(inta,intb){returndx[a]*dx[b]+dy[a]*dy[b]+dz[a]*dz[b]==0;}// 方向字符串转编号intdirToId(conststring&s){if(s=="+x")return0;if(s=="-x")return1;if(s=="+y")return2;if(s=="-y")return3;if(s=="+z")return4;return5;// "-z"}// 深度优先搜索// 当前所在立方体 (x,y,z)，正在构建第 segIdx 个段（0起始），// 段内已走步数 segStep (0~3)，本段入口方向 inDir，// mode: 0=未定, 1=模式A(入口,入口,出口), 2=模式B(入口,出口,出口)// outDir: 本段出口方向（未定时为 -1）booldfs(intx,inty,intz,intsegIdx,intsegStep,intinDir,intmode,intoutDir){// 如果段内三步已经走完if(segStep==3){// 如果是最后一段，检查是否到达出口且方向匹配if(segIdx==K-1)return(x==ex&&y==ey&&z==ez&&outDir==soutDir);// 否则需要走连接步，方向必须等于本段出口方向intd=outDir;intnx=x+dx[d],ny=y+dy[d],nz=z+dz[d];if(nx<1||nx>X||ny<1||ny>Y||nz<1||nz>Z)returnfalse;if(vis[nx][ny][nz])returnfalse;vis[nx][ny][nz]=true;boolres=dfs(nx,ny,nz,segIdx+1,0,d,0,-1);vis[nx][ny][nz]=false;returnres;}// 枚举下一步方向for(intd=0;d<6;++d){boolok=false;intnewMode=mode,newOut=outDir;if(segStep==0){// 第一步必须等于入口方向if(d==inDir)ok=true;}elseif(segStep==1){// 第二步：可选入口方向（模式A）或垂直方向（模式B）if(d==inDir){ok=true;newMode=1;// 模式AnewOut=-1;}elseif(isVertical(inDir,d)){ok=true;newMode=2;// 模式B，出口方向就是 dnewOut=d;}}elseif(segStep==2){// 第三步if(mode==1){// 模式A：第三步必须垂直于入口方向且不等于入口方向if(isVertical(inDir,d)&&d!=inDir){ok=true;newOut=d;}}elseif(mode==2){// 模式B：第三步必须等于之前确定的出口方向if(d==outDir){ok=true;newOut=outDir;}}}if(!ok)continue;intnx=x+dx[d],ny=y+dy[d],nz=z+dz[d];if(nx<1||nx>X||ny<1||ny>Y||nz<1||nz>Z)continue;if(vis[nx][ny][nz])continue;vis[nx][ny][nz]=true;boolres=false;if(segStep==0)res=dfs(nx,ny,nz,segIdx,1,inDir,0,-1);elseif(segStep==1)res=dfs(nx,ny,nz,segIdx,2,inDir,newMode,newOut);elseres=dfs(nx,ny,nz,segIdx,3,inDir,mode,newOut);vis[nx][ny][nz]=false;if(res)returntrue;}returnfalse;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intcaseNo=1;while(cin>>X&&X!=0){cin>>Y>>Z;cin>>sx>>sy>>sz;string sinStr;cin>>sinStr;cin>>ex>>ey>>ez;string soutStr;cin>>soutStr;sinDir=dirToId(sinStr);soutDir=dirToId(soutStr);intans=-1;for(K=1;K<=6;++K){memset(vis,false,sizeof(vis));vis[sx][sy][sz]=true;if(dfs(sx,sy,sz,0,0,sinDir,0,-1)){ans=K;break;}}cout<<"Case "<<caseNo++<<": ";if(ans==-1)cout<<"Impossible\n";elsecout<<ans<<'\n';}return0;}

总结

本题是一道典型的三维网格路径搜索问题，核心在于正确建模每个肘的几何形状和连接方式。由于肘数上限很小（666），采用深度优先搜索暴力枚举是完全可行的。关键技巧在于：

• 将每个肘的内部路径抽象为333步的方向序列，并明确两种合法的模式；
• 用vis数组避免立方体重复占用，保证管道无自交；
• 从小段数开始递增尝试，一旦找到即退出，保证答案最优。

本题也展示了在约束明确的情况下，暴力搜索配合适当的剪枝可以轻松解决看似复杂的三维管道设计问题。在实际竞赛中，务必仔细阅读题目并理解部件的几何细节，才能写出正确的状态转移逻辑。