Q房网入职矩阵算法题

[Turing724]

  在页面上输入 X，N。
  从 M x M 矩阵中第 X 个格子出发，水平或垂直方向任意前进 N 步，不可重复走过的格子，最终输出所有可行的路径。
  注：M 的取值由开发者自定。

 矩阵示例：M=3
  ___ ___ ___
  |_1_|_2_|_3_|
  |_4_|_5_|_6_|
  |_7_|_8_|_9_|

• 思路
  1. 将对应出发的 第 X 个格子转换成坐标。
  2. 每走一步求出当前坐标的上下左右格子数的有效性。
  3. 如若有效则+=下一步。
  4. 递归并创建一个空数组保存之前走过的路径，直到上下左右格子数失去有效性。

  // 复制之前走过的路径到一个新的空数组里
  function copyPath(step) {
    const steps = [];
    for (let i = 0; i < step.length; i++) {
      steps.push(step[i]);
    }
    return steps;
  }

  /***
   * @description 根据格子数获取对应坐标
   * @params Number m | 矩阵规格
   * @params Number value | 格子值
   * @return Number[] | [x, y] 坐标
   */
  function getCoords(m, value) {
    return [(value - 1) % m, Math.floor((value - 1) / m)];
  }
  /***
   * @description 根据坐标对应矩阵中的值且判断当前数字上下左右值的有效性
   * @params Number x | x轴
   * @params Number y | y轴
   * @params Number m | 矩阵规格
   * @return Boolean | Number
   */
  function getNum(x, y, m) {
    let col = x + 1;
    let row = y + 1;
    return col > m || row > m || x < 0 || y < 0 ? false : m * y + col;
  }

  /***
   * @description 判断方向值的有效性
   * @params Number | nextNum | 下一个步数
   * @params Number[] | list | 走过的步数集合
   * @return Boolean
   */
  function checkPath(nextNum, list) {
    return nextNum !== false && !~list.indexOf(nextNum);
  }

  /***
   * @description 矩阵获取有效路径
   * @params Number | m | 矩阵规格
   * @params Number | n | 步数
   * @params Number | initialValue | 初始值
   */
  function path(m, n, initialValue) {
    const pathList = [];
    const max = m * m;
    const [x, y] = getCoords(m, initialValue);

    function deep(x, y, step) {
      // 起始步数的值push进数组里
      step.push(getNum(x, y, m));
      // 判断当前路径的长度是否大于或等于步数
      if (step.length > n || step.length >= max) {
        pathList.push(step);
        return;
      }

      // 获取当前值对应的上下左右的值
      const left = getNum(x - 1, y, m);
      const right = getNum(x + 1, y, m);
      const up = getNum(x, y - 1, m);
      const down = getNum(x, y + 1, m);

      const directionList = [left, right, up, down];
      directionList.forEach((item) => {
        const canNext = checkPath(item, step);
        if (canNext) {
          const newPath = copyPath(step);
          const [nextX, nextY] = getCoords(m, item);
          deep(nextX, nextY, newPath);
        }
      })
      return step;
    }
    deep(x, y, [])
    return pathList;
  }

  // const pathList = path(4, 4, 6)
  // console.log('%c pathList  =>', 'color:blue;font-size:18px', pathList)
  // const pathList2 = path(4, 3, 3)
  // console.log('%c pathList2  =>', 'color:blue;font-size:18px', pathList2)
  // console.log(pathList, 'path')