15x15网格N步内可达单元格查找算法及现有JavaScript递归方案优化咨询

首先你的递归实现存在明显的无效计算问题：同一个单元格会被不同路径多次重复访问，尤其是N增大后，重复遍历的量级会指数级上升，这是性能不足的核心原因。
针对你的需求（查找N步及以内所有可达单元格），有两类优化方案：

方案1：优化现有递归实现 #

核心是加最小步数校验，避免重复遍历：

• 新增一个和棋盘尺寸一致的二维数组minStep，初始值全部设为Infinity，用来记录到达每个单元格的最少步数
• 进入递归时新增判断：如果当前已经花费的步数（即总步数N - 剩余步数n）大于等于该单元格记录的minStep，直接终止当前分支的递归，因为之前已经用更少的步数到过这里，当前分支能拓展的范围不可能超过之前的遍历结果，属于完全无效的计算
• 补充坐标边界校验，避免u/v超出15x15的数组范围导致报错

优化后的递归代码参考：

// 提前初始化minStep数组，调用递归前先重置所有值为Infinity
search(n, u, v, totalN, minStep, board) {
    const costStep = totalN - n;
    // 边界判断、墙判断、步数重复判断
    if (n == 0 || isWall(u, v) || u < 0 || u >= 15 || v <0 || v >=15 || costStep >= minStep[v][u])
        return;
        
    board[v][u] = 2;
    minStep[v][u] = costStep;
    
    search(n - 1, u, v - 1, totalN, minStep, board);
    search(n - 1, u + 1, v, totalN, minStep, board);
    search(n - 1, u, v + 1, totalN, minStep, board);
    search(n - 1, u - 1, v, totalN, minStep, board);
    
    return;
}

方案2：替换为广度优先搜索（BFS），性能更优 #

BFS天然按步数从小到大遍历单元格，每个单元格只要被访问过一次，就说明已经用最少步数到达，不需要重复遍历，时间复杂度稳定为O(网格总单元格数)，15x15的网格最多只会遍历225次，不会有递归栈溢出的风险，性能远优于递归实现。

参考代码如下：

// 参数：起点u、起点v、最大步数N、棋盘二维数组
function markReachable(startU, startV, N, board) {
    const dirs = [[0, -1], [1, 0], [0, 1], [-1, 0]]; // 上下左右四个方向
    const visited = Array.from({length: 15}, () => Array(15).fill(false));
    const queue = [[startU, startV, 0]];
    
    // 起点合法性校验
    if (startU <0 || startU >=15 || startV <0 || startV >=15 || board[startV][startU] === 1) return board;
    visited[startV][startU] = true;
    board[startV][startU] = 2;

    while(queue.length) {
        const [u, v, step] = queue.shift();
        if (step >= N) continue; // 达到最大步数，停止拓展

        for (const [du, dv] of dirs) {
            const newU = u + du;
            const newV = v + dv;
            // 校验边界、不是墙、未访问过
            if (newU >=0 && newU <15 && newV >=0 && newV <15 && board[newV][newU] !== 1 && !visited[newV][newU]) {
                visited[newV][newU] = true;
                board[newV][newU] = 2;
                queue.push([newU, newV, step + 1]);
            }
        }
    }
    return board;
}

如果需要进一步优化BFS性能，可以把普通队列替换成双端队列，或者用两个数组交替存储当前层和下一层的节点，避免shift()操作的性能损耗。

内容的提问来源于stack exchange，提问作者kaffeetasse