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)。