You need to enable JavaScript to run this app. 如何高效实现二维数组中同类相邻元素的定位分组(类SameGame场景)
优惠活动
大模型
产品
解决方案
定价
更多

如何高效实现二维数组中同类相邻元素的定位分组(类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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.31 00:57:05