题目描述

从 M x M 矩阵中第 X 个格子出发(start)，水平或垂直方向任意前进 N 步(N < M*M)，不可重复走过的格子，最终输出所有可行的路径。

eg： input：M 为 3， X 为 1，N 为 1 output: [[1, 2], [1, 4]]

/**
 * @param {int} M
 * @param {int} X
 * @param {int} N
 * @return {Array}
 * 
 */
function goGrid(M, X, N){

}

解法

点击查看

/**
 * @param {int} M
 * @param {int} X
 * @param {int} N
 * @return {Array}
 * 
 */
function goGrid(x, n, m){
    const ret = [[x]]
    if(n === 0){
        return ret
    }
    while(--n>=0){ //控制循环
        for(let i=0; i<ret.length; i++){
            const item = ret[i]
            const curr = item.pop()
            const nodes = next(curr, m).filter(x=>!item.includes(x))
            if(nodes.length){ //1拆多
                const sub = nodes.map(x=>{
                    return item.concat(curr, x)
                })
                ret.splice(i, 1, ...sub)
                i += nodes.length - 1
            }else{//后续所有点均重复，剔除
                ret.splice(i, 1)
                i -= 1
            }
        }
    }
    return ret
}

function next(x, m) {
    if (x === 1 || x === m || x === m * (m - 1) + 1 || x === m * m) { //四个角
        if (x % m === 1) { //第一列
            return [x + 1, x + m > m * m ? x - m : x + m]
        } else {//最后一列
            return [x - 1, x + m > m * m ? x - m : x + m]
        }
    }
    else if (x % m === 1 || x % m === 0 || m - x > 0 || Math.floor(x / m) === m - 1) {
        if (x % m === 0 || x % m === 1) {
            return [(x + 1) % m === 1 ? x - 1 : x + 1, x - m, x + m]
        } else {
            return [x - 1, x + 1, x + m > m * m ? x - m : x + m]
        }
    } else { //中间位置
        return [x - 1, x + 1, x - m, x + m]
    }
}

总结

思路如下：

• 先把抽象的 MxM 的矩阵使用 1,2,3 至到 M*M的数字填充成正方形数字表格具体化
• 矩阵中的格子可以分为三类，如同 M阶魔方
  • 四个角：下一步有 2个可能位置
  • 四条边（除去四个角的位置）：下一步有 3个可能位置
  • 中心部分：下一步有 4个可能位置
• 根据起始格子X的位置，可以得到下一步的可能位置，之后每一步均如此，但不能走之前走过的格子，直到第 N步完成
• 第一步可以得到一个数组，第二步数组中的每个元素会继续返回一个数组， 如同树状结构，只是每次分裂的分支数不固定，但在 0-4的范围内
• N个步骤会产生 N 层数组，如何把它们组合起来并串起来，考验的就是数据结构。
  • 这里先入为主的想到递归，但最终化繁为简用循环实现了，思路即循环一次，把一个数组分拆成多个，拆完去重拼接成新数组
  • 如果一个数组在循环内无法继续拆分，即下一步所有的点均重复，那么就将该数组移除

关键点：

• 总结出下一步位置的规律（3/10）
• 组织数据结构 （7/10）