Kimi LeetCode LCP 27. 黑盒光线反射 C语言实现-北京尧图网络

这是 LeetCode LCP 27. 黑盒光线反射的 C 语言实现。解题思路核心思想与 C 题解一致预处理所有光线循环有序集合维护已打开小孔。1. 状态定义每个状态由 (小孔序号, 方向) 组成。方向 1 表示沿 yx-1 表示沿 y-x。2. 预处理循环利用数学公式直接计算光线到达的下一个小孔无需模拟坐标。所有状态恰好被划分成若干个互不相交的循环。3. 有序集合每个循环维护一个有序数组记录该循环中已打开的小孔位置。open 时插入close 时删除。4. 查询光线从某个状态出发沿循环顺序找下一个已打开的小孔严格在循环顺序之后若找不到则循环到该集合的第一个。状态转移公式- 方向 1yx从第 i 个小孔射出 → 到达第 2(mn)-i 个小孔- 方向 -1y-x- 若 i ≤ 2m → 到达第 2m-i 个小孔- 若 i 2m → 到达第 2(2mn)-i 个小孔- 经过非角点小孔后方向翻转经过角点0, m, mn, 2mn方向不变。---C 语言代码c#include stdlib.h#include stdbool.h#include string.htypedef struct {int group_id;int loc;} StateInfo;typedef struct {int loc;int idx;} Elem;typedef struct {Elem *arr;int size;int cap;} Group;typedef struct {int n, m;int pt_count;StateInfo *groupPos; // 方向 1 (yx)StateInfo *groupNeg; // 方向 -1 (y-x)Group *groups;int group_cnt;bool *opened;} BlackBox;/* 预处理一个光线循环 */static void createGroup(BlackBox* obj, int index, int direction) {int gid obj-group_cnt;int gloc 0;while (1) {if (direction 1) {if (obj-groupPos[index].group_id ! -1) break;obj-groupPos[index].group_id gid;obj-groupPos[index].loc gloc;index obj-pt_count - index;} else {if (obj-groupNeg[index].group_id ! -1) break;obj-groupNeg[index].group_id gid;obj-groupNeg[index].loc gloc;if (index 2 * obj-m) {index 2 * obj-m - index;} else {index (2 * obj-m obj-n) * 2 - index;}}/* 非角点则翻转方向角点方向不变 */if (index ! 0 index ! obj-m index ! obj-m obj-n index ! 2 * obj-m obj-n) {direction -direction;}}}BlackBox* blackBoxCreate(int n, int m) {BlackBox* obj (BlackBox*)malloc(sizeof(BlackBox));obj-n n;obj-m m;obj-pt_count 2 * (n m);obj-group_cnt 0;obj-groupPos (StateInfo*)malloc(sizeof(StateInfo) * obj-pt_count);obj-groupNeg (StateInfo*)malloc(sizeof(StateInfo) * obj-pt_count);for (int i 0; i obj-pt_count; i) {obj-groupPos[i].group_id -1;obj-groupPos[i].loc -1;obj-groupNeg[i].group_id -1;obj-groupNeg[i].loc -1;}/* 预处理所有循环 */for (int i 0; i obj-pt_count; i) {/* 方向 1跳过角点 0 和 mn */if (i ! 0 i ! m n obj-groupPos[i].group_id -1) {createGroup(obj, i, 1);}/* 方向 -1跳过角点 m 和 2mn */if (i ! m i ! 2 * m n obj-groupNeg[i].group_id -1) {createGroup(obj, i, -1);}}obj-groups (Group*)calloc(obj-group_cnt, sizeof(Group));obj-opened (bool*)calloc(obj-pt_count, sizeof(bool));return obj;}/* 二分查找第一个 loc target_loc 的位置 */static int upper_bound(Group *g, int target_loc) {int lo 0, hi g-size;while (lo hi) {int mid (lo hi) 1;if (g-arr[mid].loc target_loc) {hi mid;} else {lo mid 1;}}return lo;}/* 二分查找第一个 (loc, idx) 的位置 */static int lower_bound(Group *g, int loc, int idx) {int lo 0, hi g-size;while (lo hi) {int mid (lo hi) 1;if (g-arr[mid].loc loc || (g-arr[mid].loc loc g-arr[mid].idx idx)) {lo mid 1;} else {hi mid;}}return lo;}/* 向有序数组中插入元素 */static void group_insert(Group *g, int loc, int idx) {int pos lower_bound(g, loc, idx);if (pos g-size g-arr[pos].loc loc g-arr[pos].idx idx) {return; /* 已存在避免重复插入 */}if (g-size g-cap) {g-cap g-cap 0 ? 4 : g-cap * 2;g-arr (Elem*)realloc(g-arr, sizeof(Elem) * g-cap);}memmove(g-arr[pos 1], g-arr[pos], sizeof(Elem) * (g-size - pos));g-arr[pos].loc loc;g-arr[pos].idx idx;g-size;}/* 从有序数组中删除元素 */static void group_remove(Group *g, int loc, int idx) {int pos lower_bound(g, loc, idx);if (pos g-size g-arr[pos].loc loc g-arr[pos].idx idx) {memmove(g-arr[pos], g-arr[pos 1], sizeof(Elem) * (g-size - pos - 1));g-size--;}}int blackBoxOpen(BlackBox* obj, int index, int direction) {/* 若小孔未打开将其所有对应状态插入到所属循环的有序集合中 */if (!obj-opened[index]) {obj-opened[index] true;if (obj-groupPos[index].group_id ! -1) {int gid obj-groupPos[index].group_id;int gloc obj-groupPos[index].loc;group_insert(obj-groups[gid], gloc, index);}if (obj-groupNeg[index].group_id ! -1) {int gid obj-groupNeg[index].group_id;int gloc obj-groupNeg[index].loc;group_insert(obj-groups[gid], gloc, index);}}/* 查询从当前状态出发沿循环顺序找下一个已打开的小孔 */StateInfo *info (direction 1) ? obj-groupPos[index] : obj-groupNeg[index];int gid info-group_id;int gloc info-loc;Group *g obj-groups[gid];int pos upper_bound(g, gloc);if (pos g-size) {return g-arr[pos].idx;}/* 循环到开头 */return g-arr[0].idx;}void blackBoxClose(BlackBox* obj, int index) {if (!obj-opened[index]) return;obj-opened[index] false;if (obj-groupPos[index].group_id ! -1) {int gid obj-groupPos[index].group_id;int gloc obj-groupPos[index].loc;group_remove(obj-groups[gid], gloc, index);}if (obj-groupNeg[index].group_id ! -1) {int gid obj-groupNeg[index].group_id;int gloc obj-groupNeg[index].loc;group_remove(obj-groups[gid], gloc, index);}}void blackBoxFree(BlackBox* obj) {if (!obj) return;free(obj-groupPos);free(obj-groupNeg);for (int i 0; i obj-group_cnt; i) {free(obj-groups[i].arr);}free(obj-groups);free(obj-opened);free(obj);}---复杂度分析- 预处理O(m n)每个状态恰好属于一个循环循环总数不超过 2(mn)。- 单次 open/closeO(log k)其中 k 为所在循环长度二分查找数组移动。由于操作次数 ≤ 10000且循环长度有限实际运行效率完全可接受。- 空间O(m n)。

Kimi LeetCode LCP 27. 黑盒光线反射 C语言实现

相关推荐

python核心语法(数据存储与运算)

11.PostgreSQ、-MySQL与MongoDB-AI应用如何选择数据库

UE5使用蓝图实现简单角色跳跃案例

更多资讯

汇编调试陷阱：CX寄存器高位残留导致LOOP异常

快捷指令从入门到肌肉记忆：高频指令分层学习与训练路径

API版本管理：核心挑战与工程实践指南

黄仁勋CES 2026演讲：算力即服务与AI未来趋势

Go语言interface{}原理与空值处理实战

ET2026打版软件增强版功能解析与应用指南

今日更新

猫狗目标检测数据集：VOC/COCO/YOLO三格式一体化实战包

HDU2017多校标程复现：算法竞赛工程化真题沙盒

Codex Sandbox 隔离环境拆解：AI Agent 的临时实验室如何运作

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？