题目分析本题描述了一个奇特的迷宫迷宫由M列N行组成边界处除两个入口外均为黑洞*。迷宫内部包含两种元素镜子用/或\表示两种状态对应镜子的两种朝向旋转909090度。镜子与激光束始终成454545度角。黑洞用*表示会完全吸收激光束。空地用.表示激光束可以穿过。激光束从迷宫的一个入口进入经过一系列镜面反射后需要从另一个出口离开。题目保证存在一种镜子朝向的配置方案使得激光束能够成功穿越迷宫。要求我们输出这种配置方案下的迷宫地图。需要注意的是激光束可以在空地上以909090度角自交即路径可以交叉。解题思路模型抽象本题的核心是寻找一种镜子的朝向组合使得从入口射入的激光束经过反射后恰好从出口射出。一个关键观察是激光束的传播路径完全由镜子的朝向决定。我们可以将迷宫建模为一个有向图节点迷宫中的每个镜子。边从一面镜子出发沿着某个方向上、右、下、左发射激光经过若干空地后到达的另一面镜子或出入口。对于每个镜子有444个可能的光线入射方向上、右、下、左。根据镜子当前的朝向/或\入射光线会被反射到特定的出射方向。方向定义为了便于处理我们定义四个方向0向上up1向右right2向下down3向左left对应的行、列偏移量为offset[4][2] { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }反射变换表镜子的两种状态与光线方向的映射关系如下当镜子为/时光线从上0入射 → 向右1出射从右1入射 → 向上0出射从下2入射 → 向左3出射从左3入射 → 向下2出射当镜子为\时光线从上0入射 → 向左3出射从右1入射 → 向下2出射从下2入射 → 向右1出射从左3入射 → 向上0出射用表格transform[2][4][2]存储第一维表示镜子状态0为/1为\第二维表示入射方向第三维的第一个元素是出射方向第二个元素是出射光线的“方向”实际上与入射方向的意义相同此处用于计算下一个镜子。图的构建对于每个镜子我们需要找出从它出发沿着444个方向直线传播时会遇到的第一个对象另一面镜子或出入口。这个过程通过模拟光线直线传播完成从当前镜子的位置(i, j)开始沿着方向d逐步移动。如果遇到黑洞*则停止光线被吸收。如果遇到空地.继续前进。如果遇到出入口边界上的空地indexer -1记录为出口reflect[m][d] -1并记录第一个镜子作为搜索起点。如果遇到另一面镜子记录它的编号停止。这样就建立了镜子之间的邻接关系reflect[m][d]表示从镜子m沿方向d出发到达的下一个镜子编号-1表示到达出口。DFS\texttt{DFS}DFS搜索策略问题的目标是确定每个镜子的朝向/或\使得从入口出发的激光最终到达出口。我们使用深度优先搜索DFS\texttt{DFS}DFS来尝试镜子的朝向状态当前所在的镜子编号mirror和入射光线的方向light。转移根据当前镜子的当前朝向计算反射后的出射方向并得到下一个镜子next_mirror递归搜索。关键点每个镜子可以有两种状态翻或不翻。在DFS\texttt{DFS}DFS中我们先尝试当前状态如果失败则翻转该镜子的状态再尝试如果仍然失败则回溯。为了避免无限循环使用visited数组记录当前搜索路径上已经访问过的镜子注意这里的“访问”是针对于一次搜索路径的而非全局永久标记。入口的确定我们需要找到激光的起始位置。题目没有明确说明哪个是入口但我们可以通过构建图的过程自然地找到第一个通过直线传播到达出口的镜子及其入射方向就是搜索的起点。具体地在构建reflect数组时如果遇到reflect[m][d] -1则记录firstMirror m和firstLight d。输出搜索完成后flapped[i]记录了第i面镜子的最终朝向1表示\0表示/。据此更新grid数组然后输出整个迷宫。多个迷宫之间用空行分隔。复杂度分析镜子数量最多为50×50250050 \times 50 250050×502500个。每个镜子有222种状态理论上状态空间为225002^{2500}22500但通过DFS\texttt{DFS}DFS回溯和图的约束实际搜索空间远小于此。构建图的时间复杂度为O(O(O(镜子数量×4×max(M,N))\times 4 \times \max(M, N))×4×max(M,N))在本题限制下完全可行。代码实现// Mirror Maze// UVa ID: 258// Verdict: Accepted// Submission Date: 2016-06-01// UVa Run Time: 0.090s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;chargrid[60][60];introw,column;intreflect[3600][4],indexer[60][60],flapped[3600],visited[3600];vectorpairint,intmirrors(3600);// 方向定义0 上1 右2 下3 左intoffset[4][2]{{-1,0},{0,1},{1,0},{0,-1}};// 反射变换表// 第一维镜子状态0 /1 \// 第二维入射方向// 第三维[0] 出射方向[1] 出射光线方向用于计算下一个镜子inttransform[2][4][2]{{{3,1},{2,0},{1,3},{0,2}},// 镜子为 /{{1,3},{0,2},{3,1},{2,0}}// 镜子为 \};// 根据当前镜子和入射光线计算下一个镜子编号和出射光线方向inlinevoidgetNextMirror(intmirror,intlight,intnext_mirror,intnext_light){next_mirrorreflect[mirror][transform[flapped[mirror]][light][0]];next_lighttransform[flapped[mirror]][light][1];}// 深度优先搜索尝试为镜子确定朝向// mirror: 当前所在的镜子编号light: 入射光线的方向booldfs(intmirror,intlight){// 到达出口-1 表示出口if(mirror-1)returntrue;// 记录当前镜子是否已经在本轮搜索路径中被访问过boolmirrorVisitedvisited[mirror];visited[mirror]true;intnext_mirror,next_light;getNextMirror(mirror,light,next_mirror,next_light);// 尝试当前镜子的当前朝向if(next_mirror!0dfs(next_mirror,next_light))returntrue;// 如果当前朝向失败且当前镜子之前未被访问过尝试翻转该镜子if(!mirrorVisited){flapped[mirror]!flapped[mirror];// 翻转状态getNextMirror(mirror,light,next_mirror,next_light);if(next_mirror!0dfs(next_mirror,next_light))returntrue;// 回溯恢复原状态flapped[mirror]!flapped[mirror];}// 恢复 visited 状态visited[mirror]mirrorVisited;returnfalse;}intmain(){boolprintBlankLinefalse;// 读取多个迷宫以 -1 -1 结束while(cincolumnrow,column0row0){// 初始化数组memset(indexer,0,sizeof(indexer));memset(flapped,0,sizeof(flapped));memset(visited,0,sizeof(visited));memset(reflect,0,sizeof(reflect));intmirrorNumber0;// 读取迷宫地图for(inti0;irow;i)for(intj0;jcolumn;j){cingrid[i][j];// 边界上的空地视为出入口编号为 -1if(grid[i][j].(i0||i(row-1)||j0||j(column-1)))indexer[i][j]-1;elseif(grid[i][j]/||grid[i][j]\\){mirrorNumber;mirrors[mirrorNumber]make_pair(i,j);// 记录镜子的初始状态\ 为 1/ 为 0flapped[mirrorNumber](grid[i][j]\\);indexer[i][j]mirrorNumber;}}// 构建镜子之间的连接关系intfirstMirror-1,firstLight-1;for(intm1;mmirrorNumber;m)for(intd0;d4;d){intimirrors[m].first,jmirrors[m].second;while(true){ioffset[d][0],joffset[d][1];// 遇到黑洞停止if(grid[i][j]*)break;// 遇到出入口if(indexer[i][j]-1){reflect[m][d]-1;// 记录第一个镜子及其入射方向作为搜索起点firstMirrorm;firstLightd;break;}// 遇到另一面镜子if(indexer[i][j]0){reflect[m][d]indexer[i][j];break;}}}// 从起点开始 DFS 搜索if(firstMirror!-1firstLight!-1)dfs(firstMirror,firstLight);// 输出结果迷宫之间用空行分隔if(printBlankLine)coutendl;elseprintBlankLinetrue;// 根据 flapped 数组更新地图中的镜子朝向for(inti1;imirrorNumber;i)grid[mirrors[i].first][mirrors[i].second](flapped[i]?\\:/);// 输出迷宫for(inti0;irow;i){for(intj0;jcolumn;j)coutgrid[i][j];coutendl;}}return0;}
UVa 258 Mirror Maze
题目分析本题描述了一个奇特的迷宫迷宫由M列N行组成边界处除两个入口外均为黑洞*。迷宫内部包含两种元素镜子用/或\表示两种状态对应镜子的两种朝向旋转909090度。镜子与激光束始终成454545度角。黑洞用*表示会完全吸收激光束。空地用.表示激光束可以穿过。激光束从迷宫的一个入口进入经过一系列镜面反射后需要从另一个出口离开。题目保证存在一种镜子朝向的配置方案使得激光束能够成功穿越迷宫。要求我们输出这种配置方案下的迷宫地图。需要注意的是激光束可以在空地上以909090度角自交即路径可以交叉。解题思路模型抽象本题的核心是寻找一种镜子的朝向组合使得从入口射入的激光束经过反射后恰好从出口射出。一个关键观察是激光束的传播路径完全由镜子的朝向决定。我们可以将迷宫建模为一个有向图节点迷宫中的每个镜子。边从一面镜子出发沿着某个方向上、右、下、左发射激光经过若干空地后到达的另一面镜子或出入口。对于每个镜子有444个可能的光线入射方向上、右、下、左。根据镜子当前的朝向/或\入射光线会被反射到特定的出射方向。方向定义为了便于处理我们定义四个方向0向上up1向右right2向下down3向左left对应的行、列偏移量为offset[4][2] { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }反射变换表镜子的两种状态与光线方向的映射关系如下当镜子为/时光线从上0入射 → 向右1出射从右1入射 → 向上0出射从下2入射 → 向左3出射从左3入射 → 向下2出射当镜子为\时光线从上0入射 → 向左3出射从右1入射 → 向下2出射从下2入射 → 向右1出射从左3入射 → 向上0出射用表格transform[2][4][2]存储第一维表示镜子状态0为/1为\第二维表示入射方向第三维的第一个元素是出射方向第二个元素是出射光线的“方向”实际上与入射方向的意义相同此处用于计算下一个镜子。图的构建对于每个镜子我们需要找出从它出发沿着444个方向直线传播时会遇到的第一个对象另一面镜子或出入口。这个过程通过模拟光线直线传播完成从当前镜子的位置(i, j)开始沿着方向d逐步移动。如果遇到黑洞*则停止光线被吸收。如果遇到空地.继续前进。如果遇到出入口边界上的空地indexer -1记录为出口reflect[m][d] -1并记录第一个镜子作为搜索起点。如果遇到另一面镜子记录它的编号停止。这样就建立了镜子之间的邻接关系reflect[m][d]表示从镜子m沿方向d出发到达的下一个镜子编号-1表示到达出口。DFS\texttt{DFS}DFS搜索策略问题的目标是确定每个镜子的朝向/或\使得从入口出发的激光最终到达出口。我们使用深度优先搜索DFS\texttt{DFS}DFS来尝试镜子的朝向状态当前所在的镜子编号mirror和入射光线的方向light。转移根据当前镜子的当前朝向计算反射后的出射方向并得到下一个镜子next_mirror递归搜索。关键点每个镜子可以有两种状态翻或不翻。在DFS\texttt{DFS}DFS中我们先尝试当前状态如果失败则翻转该镜子的状态再尝试如果仍然失败则回溯。为了避免无限循环使用visited数组记录当前搜索路径上已经访问过的镜子注意这里的“访问”是针对于一次搜索路径的而非全局永久标记。入口的确定我们需要找到激光的起始位置。题目没有明确说明哪个是入口但我们可以通过构建图的过程自然地找到第一个通过直线传播到达出口的镜子及其入射方向就是搜索的起点。具体地在构建reflect数组时如果遇到reflect[m][d] -1则记录firstMirror m和firstLight d。输出搜索完成后flapped[i]记录了第i面镜子的最终朝向1表示\0表示/。据此更新grid数组然后输出整个迷宫。多个迷宫之间用空行分隔。复杂度分析镜子数量最多为50×50250050 \times 50 250050×502500个。每个镜子有222种状态理论上状态空间为225002^{2500}22500但通过DFS\texttt{DFS}DFS回溯和图的约束实际搜索空间远小于此。构建图的时间复杂度为O(O(O(镜子数量×4×max(M,N))\times 4 \times \max(M, N))×4×max(M,N))在本题限制下完全可行。代码实现// Mirror Maze// UVa ID: 258// Verdict: Accepted// Submission Date: 2016-06-01// UVa Run Time: 0.090s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;chargrid[60][60];introw,column;intreflect[3600][4],indexer[60][60],flapped[3600],visited[3600];vectorpairint,intmirrors(3600);// 方向定义0 上1 右2 下3 左intoffset[4][2]{{-1,0},{0,1},{1,0},{0,-1}};// 反射变换表// 第一维镜子状态0 /1 \// 第二维入射方向// 第三维[0] 出射方向[1] 出射光线方向用于计算下一个镜子inttransform[2][4][2]{{{3,1},{2,0},{1,3},{0,2}},// 镜子为 /{{1,3},{0,2},{3,1},{2,0}}// 镜子为 \};// 根据当前镜子和入射光线计算下一个镜子编号和出射光线方向inlinevoidgetNextMirror(intmirror,intlight,intnext_mirror,intnext_light){next_mirrorreflect[mirror][transform[flapped[mirror]][light][0]];next_lighttransform[flapped[mirror]][light][1];}// 深度优先搜索尝试为镜子确定朝向// mirror: 当前所在的镜子编号light: 入射光线的方向booldfs(intmirror,intlight){// 到达出口-1 表示出口if(mirror-1)returntrue;// 记录当前镜子是否已经在本轮搜索路径中被访问过boolmirrorVisitedvisited[mirror];visited[mirror]true;intnext_mirror,next_light;getNextMirror(mirror,light,next_mirror,next_light);// 尝试当前镜子的当前朝向if(next_mirror!0dfs(next_mirror,next_light))returntrue;// 如果当前朝向失败且当前镜子之前未被访问过尝试翻转该镜子if(!mirrorVisited){flapped[mirror]!flapped[mirror];// 翻转状态getNextMirror(mirror,light,next_mirror,next_light);if(next_mirror!0dfs(next_mirror,next_light))returntrue;// 回溯恢复原状态flapped[mirror]!flapped[mirror];}// 恢复 visited 状态visited[mirror]mirrorVisited;returnfalse;}intmain(){boolprintBlankLinefalse;// 读取多个迷宫以 -1 -1 结束while(cincolumnrow,column0row0){// 初始化数组memset(indexer,0,sizeof(indexer));memset(flapped,0,sizeof(flapped));memset(visited,0,sizeof(visited));memset(reflect,0,sizeof(reflect));intmirrorNumber0;// 读取迷宫地图for(inti0;irow;i)for(intj0;jcolumn;j){cingrid[i][j];// 边界上的空地视为出入口编号为 -1if(grid[i][j].(i0||i(row-1)||j0||j(column-1)))indexer[i][j]-1;elseif(grid[i][j]/||grid[i][j]\\){mirrorNumber;mirrors[mirrorNumber]make_pair(i,j);// 记录镜子的初始状态\ 为 1/ 为 0flapped[mirrorNumber](grid[i][j]\\);indexer[i][j]mirrorNumber;}}// 构建镜子之间的连接关系intfirstMirror-1,firstLight-1;for(intm1;mmirrorNumber;m)for(intd0;d4;d){intimirrors[m].first,jmirrors[m].second;while(true){ioffset[d][0],joffset[d][1];// 遇到黑洞停止if(grid[i][j]*)break;// 遇到出入口if(indexer[i][j]-1){reflect[m][d]-1;// 记录第一个镜子及其入射方向作为搜索起点firstMirrorm;firstLightd;break;}// 遇到另一面镜子if(indexer[i][j]0){reflect[m][d]indexer[i][j];break;}}}// 从起点开始 DFS 搜索if(firstMirror!-1firstLight!-1)dfs(firstMirror,firstLight);// 输出结果迷宫之间用空行分隔if(printBlankLine)coutendl;elseprintBlankLinetrue;// 根据 flapped 数组更新地图中的镜子朝向for(inti1;imirrorNumber;i)grid[mirrors[i].first][mirrors[i].second](flapped[i]?\\:/);// 输出迷宫for(inti0;irow;i){for(intj0;jcolumn;j)coutgrid[i][j];coutendl;}}return0;}
