打开转盘锁

题目

题目来源：力扣（LeetCode）

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:

输入：deadends = [“0201”,”0101”,”0102”,”1212”,”2002”], target = “0202”
输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，
因为当拨动到 “0102” 时这个锁就会被锁定。

示例 2:

输入: deadends = [“8888”], target = “0009”
输出：1
解释：
把最后一位反向旋转一次即可 “0000” -> “0009”。

示例 3:

输入: deadends = [“8887”,”8889”,”8878”,”8898”,”8788”,”8988”,”7888”,”9888”], target = “8888”
输出：-1
解释：
无法旋转到目标数字且不被锁定。

示例 4:

输入: deadends = [“0000”], target = “8888”
输出：-1

// 1.一个拨轮拨动一次，只有两种选择：向上，向下（要注意0、9边界性）。
// 2.当前有四个拨轮，所以选择一个拨轮拨动一次时，有 2 * 4 种可能性。
// 3.在这次选择的基础上，进行下一次选择，又有8种可能性，依次类推 。
var openLock = function (deadends, target) {
  let path = '0000';
  const queue = [path];
  const visited = {}; // 已访问节点
  const dead = {}; // deadends死节点
  let step = 0; // 最少拨动次数
  const swipeUp = (path, index) => { // 向上拨动一个数字
    const arr = path.split('');
    if (arr[index] === '9') { // 如果数字已经转到了 9, 则重新从 0 开始转
      arr[index] = '0';
    } else {
      arr[index]++; // 拨动一个数字
    }
    return arr.join('');
  };
  const swipeDown = (path, index) => { // 向下拨动一个数字
    const arr = path.split('');
    if (arr[index] === '0') { // 如果数字已经转到了0, 则重新从 9 开始转
      arr[index] = '9';
    } else {
      arr[index]--; // 往下拨动一个数字
    }
    return arr.join('');
  };
  for (let num of deadends) {
    dead[num] = true;
  }
  while (queue.length) {
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      const password = queue.shift();
      if (dead[password]) continue; // 剪枝
      if (password === target) return step; // 找到答案
      for (let j = 0; j < 4; j++) {
        const upPassword = swipeUp(password, j);
        console.log('==upPassword==',upPassword);
        const downPassword = swipeDown(password, j);
        console.log('==downPassword==',downPassword);
        !visited[upPassword] && queue.push(upPassword) &&
          (visited[upPassword] = true); // 剪枝
        !visited[downPassword] && queue.push(downPassword) &&
          (visited[downPassword] = true); // 剪枝
      }
    }
    step++;
  }
  return -1;
};