如何高效实现二维数组中同类相邻元素的定位分组(类SameGame场景)
SameGame 同类相邻元素定位的性能优化方案
你遇到的场景本质是二维网格4连通域查找问题,无需手写零散的邻接判断分支,有成熟实现方式,性能优于零散拆分支的手写逻辑,且不会出现逻辑漏判、重复遍历的问题。
核心实现逻辑
整体遍历全程保证每个格子只被处理一次,时间复杂度为O(总格子数),是这类问题的理论最优性能。
- 初始化两个和棋盘同尺寸的辅助结构:一个用来标记已被归入某个相邻块的格子,避免重复处理;另一个用来存储每个相邻块包含的所有坐标,直接支持高亮需求
- 逐格遍历棋盘,遇到未被标记的格子时,以它为起点查找所有连通的同值元素:
- 统一通过方向数组遍历上下左右4个相邻位置,无需为每个方向单独写判断分支
- 只要相邻位置在棋盘边界内、未被标记、且和起点元素值相同,就将它归入当前块,标记为已处理
- 所有连通元素探测完成后,记录当前块的坐标集合即可
核心实现参考代码
// 定义四个相邻方向:上、下、左、右,替代零散的x+1/y-1分支判断 const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // 初始化访问标记数组,和棋盘尺寸一致 let visited = Array.from({length: row}, () => new Array(col).fill(false)); // 存储所有相邻同类块的集合 let allAdjacentGroups = []; for (let i = 0; i < row; i++) { for (let j = 0; j < col; j++) { // 已处理过的格子直接跳过 if (visited[i][j]) continue; // 以当前格子为起点,查找它所属的连通同类块 const blockColor = tab[i][j]; let currentBlock = []; // 用栈结构存储待探测的坐标,避免递归栈溢出问题 let probeStack = [[i, j]]; visited[i][j] = true; while (probeStack.length) { const [x, y] = probeStack.pop(); currentBlock.push([x, y]); // 统一遍历四个方向的邻居 for (const [dx, dy] of DIRS) { const nextX = x + dx; const nextY = y + dy; // 统一做边界校验、访问校验、值匹配校验 const isValid = nextX >= 0 && nextX < row && nextY >=0 && nextY < col && !visited[nextX][nextY] && tab[nextX][nextY] === blockColor; if (isValid) { visited[nextX][nextY] = true; probeStack.push([nextX, nextY]); } } } allAdjacentGroups.push(currentBlock); } }
适配小游戏场景的优化细节
- 小尺寸棋盘(比如3行4列的初始场景)下,上述实现的性能开销可以忽略不计,哪怕后续棋盘扩展到几十行乘几十列,也不会出现卡顿
- 如果需求是点击某个格子时,高亮它所在的同类相邻块,完全不需要提前预计算所有连通块:只需要从用户点击的格子位置出发,跑一次连通域探测即可,性能开销更低
- 现有随机生成棋盘的逻辑完全兼容,不需要改动:随机生成完所有格子的元素值后,跑一次上述标记流程,就能拿到所有相邻同类块的位置集合,直接对接高亮逻辑即可
对比你现有实现的优势
- 无重复遍历:每个格子最多被访问一次,不会出现同一个格子被多个邻接判断逻辑重复扫描的情况
- 逻辑收敛:所有邻接判断、边界校验的逻辑集中在统一的代码块里,不会因为零散写if分支出现漏判(比如漏判左邻居、上邻居的情况)
- 后续扩展方便:可以直接从存储的块集合里读取块大小、块内坐标,支持后续消除、可点状态判断等SameGame核心逻辑,不用临时重新遍历
内容的提问来源于stack exchange,提问作者Lucas Grandjean
相关产品推荐
相关产品推荐

