这道题的核心是预处理 有序集合。 解题思路光线路径的循环性在黑盒中从任意小孔沿某方向射入的光线最终都会回到起点并沿相同方向射出形成一个闭合的“循环”。在所有小孔都关闭的情况下光线会在循环中无限反射。状态表示每一个(小孔编号, 方向)的组合都代表了光线在循环中的一个“状态”。状态总数是2 * (2*(mn)) - 4 4(mn)-4。开启小孔的作用开启一个小孔相当于在它所属的循环路径上将该小孔对应的“状态位置”标记为“出口”。查询的本质open操作就是在当前光线状态所处的循环中查找该状态位置之后的第一个“出口”。高效数据结构使用TreeSet维护每个循环上所有已开启小孔的位置可以高效地完成“查找下一个”和“插入/删除”操作。☕️ Java 代码实现importjava.util.*;classBlackBox{privatefinalintn,m;privatefinalinttotalHoles;// 小孔总数: 2 * (m n)privatefinalinttotalStates;// 状态总数: 4 * (m n) - 4// cycleId[hole][dirIndex]: 记录状态 (hole, direction) 所属的循环ID// posInCycle[hole][dirIndex]: 记录状态在所属循环中的位置privatefinalint[][]cycleId;privatefinalint[][]posInCycle;// 每个循环对应一个 TreeSet存储该循环上所有已开启小孔的位置privatefinalListTreeSetIntegercycles;privateintcycleCount;publicBlackBox(intn,intm){this.nn;this.mm;this.totalHoles2*(mn);this.totalStates4*(mn)-4;this.cycleIdnewint[totalHoles][2];this.posInCyclenewint[totalHoles][2];// 初始化-1 表示该状态尚未被分配循环for(inti0;itotalHoles;i){Arrays.fill(cycleId[i],-1);Arrays.fill(posInCycle[i],-1);}this.cyclesnewArrayList();this.cycleCount0;// 在构造函数中预处理所有循环findAllCycles();}// 预处理所有光线的循环路径privatevoidfindAllCycles(){for(intstartHole0;startHoletotalHoles;startHole){for(intstartDir:newint[]{1,-1}){// 拐角处的小孔只有一个合法方向if(isCorner(startHole)!isValidCornerDirection(startHole,startDir)){continue;}intdirIdxdirToIndex(startDir);// 如果这个状态已经属于某个循环则跳过if(cycleId[startHole][dirIdx]!-1){continue;}// 发现一个新循环TreeSetIntegercycleSetnewTreeSet();intcurrentCycleIdcycleCount;cycles.add(cycleSet);intcurHolestartHole;intcurDirstartDir;intpos0;// 沿着光线路径前进直到回到起点状态do{// 记录当前状态cycleId[curHole][dirToIndex(curDir)]currentCycleId;posInCycle[curHole][dirToIndex(curDir)]pos;// 计算下一个状态: 经过小孔 curHole 后方向取反intnextDir-curDir;// 计算从 (curHole, nextDir) 出发到达的下一个小孔编号intnextHolegetNextHole(curHole,nextDir);curHolenextHole;curDirnextDir;pos;}while(!(curHolestartHolecurDirstartDir));}}}// 判断小孔是否为四个拐角privatebooleanisCorner(inthole){returnhole0||holem||holemn||hole2*mn;}// 判断拐角处的方向是否合法privatebooleanisValidCornerDirection(inthole,intdir){if(hole0)returndir-1;if(holem)returndir1;if(holemn)returndir-1;if(hole2*mn)returndir1;returntrue;}// 将方向 (1 或 -1) 映射到数组索引 (0 或 1)privateintdirToIndex(intdir){returndir1?0:1;}// 核心函数给定当前小孔和下一步方向计算到达的下一个小孔编号privateintgetNextHole(inthole,intdir){intnext;if(dir1){// 沿 yx 方向// 关于 (mn) 对称next2*(mn)-hole;}else{// dir -1, 沿 y-x 方向if(hole2*m){next2*m-hole;}else{next2*(2*mn)-hole;}}// 取模运算确保结果在 [0, totalHoles) 范围内return(next%totalHolestotalHoles)%totalHoles;}// 开启小孔并射入光线返回射出的小孔编号publicintopen(intindex,intdirection){// 1. 打开小孔将小孔在两个方向上的状态位置都加入到对应的循环中for(intd:newint[]{1,-1}){intcycleIdxcycleId[index][dirToIndex(d)];if(cycleIdx!-1){intposposInCycle[index][dirToIndex(d)];cycles.get(cycleIdx).add(pos);}}// 2. 执行查询返回光线射出的小孔returnshoot(index,direction);}// 关闭小孔publicvoidclose(intindex){// 从小孔所属的所有循环中移除其位置记录for(intd:newint[]{1,-1}){intcycleIdxcycleId[index][dirToIndex(d)];if(cycleIdx!-1){intposposInCycle[index][dirToIndex(d)];cycles.get(cycleIdx).remove(pos);}}}// 内部查询方法从 (index, direction) 状态出发寻找下一个开启的小孔privateintshoot(intindex,intdirection){intdirIdxdirToIndex(direction);intcycleIdxcycleId[index][dirIdx];intcurPosposInCycle[index][dirIdx];TreeSetIntegercycleSetcycles.get(cycleIdx);// 在循环中寻找位置大于 curPos 的开启小孔IntegernextPoscycleSet.higher(curPos);if(nextPosnull){// 如果没有更大的则取循环中最小的开启小孔绕一圈nextPoscycleSet.first();}// 根据位置找到对应的小孔编号returnfindHoleByPos(cycleIdx,nextPos);}// 根据循环ID和位置找到对应的小孔编号privateintfindHoleByPos(intcycleIdx,intpos){for(inthole0;holetotalHoles;hole){for(intd:newint[]{1,-1}){if(cycleId[hole][dirToIndex(d)]cycleIdxposInCycle[hole][dirToIndex(d)]pos){returnhole;}}}return-1;// 正常情况下不会发生}} 关键点说明findAllCycles()这是预处理的核心。它遍历所有可能的起始状态(startHole, startDir)模拟光路直到回到起点从而发现一个完整的循环。getNextHole()这个函数是模拟光路的基础。它利用黑盒的几何对称性通过数学计算直接得出光线经过反射后到达的下一个小孔编号。TreeSet这是实现高效查询的关键。它维护了每个循环上当前所有开启小孔的位置pos。add(pos)/remove(pos)用于open和close操作。higher(curPos)用于shoot可以O(log N)地找到当前位置之后的下一个出口。二维数组记录状态cycleId和posInCycle两个二维数组以[hole][dirIndex]为索引记录了每个状态所属的循环和位置是后续所有操作的基础。⏱️ 复杂度分析时间复杂度预处理 (findAllCycles)需要遍历所有O(totalStates)个状态因此时间复杂度为O(n m)。open/close/shoot主要操作是TreeSet的add、remove和higher时间复杂度均为O(log K)其中 K 是该循环上已开启的小孔数量。空间复杂度需要存储所有状态的信息和TreeSet整体空间复杂度为O(n m)。
这道题的核心是预处理 有序集合。 解题思路光线路径的循环性在黑盒中从任意小孔沿某方向射入的光线最终都会回到起点并沿相同方向射出形成一个闭合的“循环”。在所有小孔都关闭的情况下光线会在循环中无限反射。状态表示每一个(小孔编号, 方向)的组合都代表了光线在循环中的一个“状态”。状态总数是2 * (2*(mn)) - 4 4(mn)-4。开启小孔的作用开启一个小孔相当于在它所属的循环路径上将该小孔对应的“状态位置”标记为“出口”。查询的本质open操作就是在当前光线状态所处的循环中查找该状态位置之后的第一个“出口”。高效数据结构使用TreeSet维护每个循环上所有已开启小孔的位置可以高效地完成“查找下一个”和“插入/删除”操作。☕️ Java 代码实现importjava.util.*;classBlackBox{privatefinalintn,m;privatefinalinttotalHoles;// 小孔总数: 2 * (m n)privatefinalinttotalStates;// 状态总数: 4 * (m n) - 4// cycleId[hole][dirIndex]: 记录状态 (hole, direction) 所属的循环ID// posInCycle[hole][dirIndex]: 记录状态在所属循环中的位置privatefinalint[][]cycleId;privatefinalint[][]posInCycle;// 每个循环对应一个 TreeSet存储该循环上所有已开启小孔的位置privatefinalListTreeSetIntegercycles;privateintcycleCount;publicBlackBox(intn,intm){this.nn;this.mm;this.totalHoles2*(mn);this.totalStates4*(mn)-4;this.cycleIdnewint[totalHoles][2];this.posInCyclenewint[totalHoles][2];// 初始化-1 表示该状态尚未被分配循环for(inti0;itotalHoles;i){Arrays.fill(cycleId[i],-1);Arrays.fill(posInCycle[i],-1);}this.cyclesnewArrayList();this.cycleCount0;// 在构造函数中预处理所有循环findAllCycles();}// 预处理所有光线的循环路径privatevoidfindAllCycles(){for(intstartHole0;startHoletotalHoles;startHole){for(intstartDir:newint[]{1,-1}){// 拐角处的小孔只有一个合法方向if(isCorner(startHole)!isValidCornerDirection(startHole,startDir)){continue;}intdirIdxdirToIndex(startDir);// 如果这个状态已经属于某个循环则跳过if(cycleId[startHole][dirIdx]!-1){continue;}// 发现一个新循环TreeSetIntegercycleSetnewTreeSet();intcurrentCycleIdcycleCount;cycles.add(cycleSet);intcurHolestartHole;intcurDirstartDir;intpos0;// 沿着光线路径前进直到回到起点状态do{// 记录当前状态cycleId[curHole][dirToIndex(curDir)]currentCycleId;posInCycle[curHole][dirToIndex(curDir)]pos;// 计算下一个状态: 经过小孔 curHole 后方向取反intnextDir-curDir;// 计算从 (curHole, nextDir) 出发到达的下一个小孔编号intnextHolegetNextHole(curHole,nextDir);curHolenextHole;curDirnextDir;pos;}while(!(curHolestartHolecurDirstartDir));}}}// 判断小孔是否为四个拐角privatebooleanisCorner(inthole){returnhole0||holem||holemn||hole2*mn;}// 判断拐角处的方向是否合法privatebooleanisValidCornerDirection(inthole,intdir){if(hole0)returndir-1;if(holem)returndir1;if(holemn)returndir-1;if(hole2*mn)returndir1;returntrue;}// 将方向 (1 或 -1) 映射到数组索引 (0 或 1)privateintdirToIndex(intdir){returndir1?0:1;}// 核心函数给定当前小孔和下一步方向计算到达的下一个小孔编号privateintgetNextHole(inthole,intdir){intnext;if(dir1){// 沿 yx 方向// 关于 (mn) 对称next2*(mn)-hole;}else{// dir -1, 沿 y-x 方向if(hole2*m){next2*m-hole;}else{next2*(2*mn)-hole;}}// 取模运算确保结果在 [0, totalHoles) 范围内return(next%totalHolestotalHoles)%totalHoles;}// 开启小孔并射入光线返回射出的小孔编号publicintopen(intindex,intdirection){// 1. 打开小孔将小孔在两个方向上的状态位置都加入到对应的循环中for(intd:newint[]{1,-1}){intcycleIdxcycleId[index][dirToIndex(d)];if(cycleIdx!-1){intposposInCycle[index][dirToIndex(d)];cycles.get(cycleIdx).add(pos);}}// 2. 执行查询返回光线射出的小孔returnshoot(index,direction);}// 关闭小孔publicvoidclose(intindex){// 从小孔所属的所有循环中移除其位置记录for(intd:newint[]{1,-1}){intcycleIdxcycleId[index][dirToIndex(d)];if(cycleIdx!-1){intposposInCycle[index][dirToIndex(d)];cycles.get(cycleIdx).remove(pos);}}}// 内部查询方法从 (index, direction) 状态出发寻找下一个开启的小孔privateintshoot(intindex,intdirection){intdirIdxdirToIndex(direction);intcycleIdxcycleId[index][dirIdx];intcurPosposInCycle[index][dirIdx];TreeSetIntegercycleSetcycles.get(cycleIdx);// 在循环中寻找位置大于 curPos 的开启小孔IntegernextPoscycleSet.higher(curPos);if(nextPosnull){// 如果没有更大的则取循环中最小的开启小孔绕一圈nextPoscycleSet.first();}// 根据位置找到对应的小孔编号returnfindHoleByPos(cycleIdx,nextPos);}// 根据循环ID和位置找到对应的小孔编号privateintfindHoleByPos(intcycleIdx,intpos){for(inthole0;holetotalHoles;hole){for(intd:newint[]{1,-1}){if(cycleId[hole][dirToIndex(d)]cycleIdxposInCycle[hole][dirToIndex(d)]pos){returnhole;}}}return-1;// 正常情况下不会发生}} 关键点说明findAllCycles()这是预处理的核心。它遍历所有可能的起始状态(startHole, startDir)模拟光路直到回到起点从而发现一个完整的循环。getNextHole()这个函数是模拟光路的基础。它利用黑盒的几何对称性通过数学计算直接得出光线经过反射后到达的下一个小孔编号。TreeSet这是实现高效查询的关键。它维护了每个循环上当前所有开启小孔的位置pos。add(pos)/remove(pos)用于open和close操作。higher(curPos)用于shoot可以O(log N)地找到当前位置之后的下一个出口。二维数组记录状态cycleId和posInCycle两个二维数组以[hole][dirIndex]为索引记录了每个状态所属的循环和位置是后续所有操作的基础。⏱️ 复杂度分析时间复杂度预处理 (findAllCycles)需要遍历所有O(totalStates)个状态因此时间复杂度为O(n m)。open/close/shoot主要操作是TreeSet的add、remove和higher时间复杂度均为O(log K)其中 K 是该循环上已开启的小孔数量。空间复杂度需要存储所有状态的信息和TreeSet整体空间复杂度为O(n m)。
