// BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多

// 计算从起点 start 到终点 target 的最近距离
function bfs(start, target) {
  const queue = []; // 核心数据结构
  const visited = new Set(); // 避免走回头路, 如果是对树处理就可以不需要visited了

  queue.push(start); // 将起点加入队列
  visited.add(start); // 记录扩散的步数
  let level = 0;

  while (queue.length) {
    const len = queue.length;
    /* 将当前队列中的所有节点向四周扩散 */
    for (let i = 0; i < len; i++) {
      const cur = queue.shift();
      /* 划重点：这里判断是否到达终点 */
      if (cur === target) {
        return level;
      }
      /* 将 cur 的相邻节点加入队列 */
      for (let x of cur.neighbors) {
        if (visited.has(x) === false) {
          queue.push(x);
          visited.add(x);
        }
      }
    }
    /* 划重点：更新步数在这里 */
    level++;
  }
}

/*
 * @lc app=leetcode.cn id=111 lang=javascript
 *
 * [111] 二叉树的最小深度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
  if (!root) return 0;
  const queue = [root];
  let depth = 1,
    cur;
  while (queue.length) {
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      cur = queue.shift();
      if (!cur.left && !cur.right) return depth;
      cur.left && queue.push(cur.left);
      cur.right && queue.push(cur.right);
    }
    depth++;
  }
  return depth;
};

// @lc code=end

/*
 * @lc app=leetcode.cn id=107 lang=javascript
 *
 * [107] 二叉树的层次遍历 II
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
  if (!root) return [];
  let queue = [];
  let levelArr = [];
  let res = [];
  queue.push(root);
  queue.push("#");
  while (queue.length) {
    let p = queue.shift();
    if (p === "#") {
      res.push(levelArr);
      levelArr = [];
      queue.length && queue.push("#");
    } else {
      levelArr.push(p.val);
      p.left && queue.push(p.left);
      p.right && queue.push(p.right);
    }
  }
  return res.reverse();
};

/*
 * @lc app=leetcode.cn id=752 lang=javascript
 *
 * [752] 打开转盘锁
 */

// @lc code=start
/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function(deadends, target) {
  const deads = new Set(deadends);
  const queue = [];
  const visited = new Set();
  queue.push("0000");
  visited.add("0000");
  let step = 0,
    cur,
    len,
    i,
    j;

  while (queue.length) {
    len = queue.length;
    for (i = 0; i < len; i++) {
      cur = queue.shift();
      if (cur === target) return step;
      if (deads.has(cur)) continue;
      for (j = 0; j < 4; j++) {
        const up = addOne(cur, j);
        if (!visited.has(up)) {
          queue.push(up);
          visited.add(up);
        }

        const down = minusOne(cur, j);
        if (!visited.has(down)) {
          queue.push(down);
          visited.add(down);
        }
      }
    }
    step++;
  }
  return -1;
};

function addOne(str, position) {
  str = str.split("");
  let cur = +str[position];
  cur = (cur + 1) % 10;
  str[position] = cur;
  return str.join("");
}
function minusOne(str, position) {
  str = str.split("");
  let cur = +str[position];
  cur = (cur - 1 + 10) % 10;
  str[position] = cur;
  return str.join("");
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=127 lang=javascript
 *
 * [127] 单词接龙
 */

// @lc code=start
/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
  const wordSize = beginWord.length;
  const allow = new Set(wordList);
  if (!allow.has(endWord)) return 0;
  const queue = [beginWord];
  const visited = new Set(queue);
  let step = 1,
    len,
    i,
    j,
    k,
    newWord,
    cur;
  while (queue.length) {
    len = queue.length;
    for (i = 0; i < len; i++) {
      cur = queue.shift();
      if (cur === endWord) return step;
      for (j = 0; j < wordSize; j++) {
        for (k = 0; k < 26; k++) {
          newWord = getNewWord(cur, j, k);
          if (newWord !== cur && allow.has(newWord) && !visited.has(newWord)) {
            queue.push(newWord);
            visited.add(newWord);
          }
        }
      }
    }
    step++;
  }
  return 0;
};

function getNewWord(str, pos, letter) {
  str = str.split("");
  str[pos] = String.fromCharCode(letter + 97);
  return str.join("");
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=773 lang=javascript
 *
 * [773] 滑动谜题
 */

// @lc code=start
/**
 * @param {number[][]} board
 * @return {number}
 */
var slidingPuzzle = function(board) {
  let start = board[0].concat(board[1]).join("");
  const target = "123450";
  const neighborMap = [
    [1, 3],
    [0, 2, 4],
    [1, 5],
    [0, 4],
    [1, 3, 5],
    [2, 4],
  ];
  let queue = [start];
  let visited = new Set(queue);
  let step = 0;

  while (queue.length) {
    let len = queue.length;
    for (let i = 0; i < len; i++) {
      let curBoard = queue.shift();
      if (curBoard === target) {
        return step;
      }
      let zeroIndex = curBoard.indexOf("0");

      let neighbor = neighborMap[zeroIndex];
      neighbor.forEach((neighborPos) => {
        let newBoard = swap(curBoard, zeroIndex, neighborPos);

        if (!visited.has(newBoard)) {
          queue.push(newBoard);
          visited.add(newBoard);
        }
      });
    }
    step++;
  }
  return -1;
};

function swap(str, i, j) {
  str = str.split("");
  [str[i], str[j]] = [str[j], str[i]];
  return str.join("");
}
// @lc code=end

var leetcodeXXX = function(nums) {
  let res = [];
  let track = [];

  function backtrack(start) {
    if (满足条件) {
      // 将当前所做的选择列表传入结果列表中
      res.push(track.slice());
      return;
    }
    for (
      let i = start /* 这里取0还是取start需要看具体情况 */;
      i < nums.length;
      i++
    ) {
      // 减枝操作
      // 判断哪些情况下可以跳过,这一步也可以放到子递归中去处理
      if (需要跳过) continue;

      // 做出选择
      track.push(nums[i]);
      // 拿着刚刚做出的选择看结果
      backtrack(i + 1);
      // 撤回刚刚做出的选择
      track.pop(nums[i]);
    }
  }
  // 启动回溯算法
  backtrack();
  return res;
};

/*
 * @lc app=leetcode.cn id=46 lang=javascript
 *
 * [46] 全排列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  let res = [];
  let track = [];
  function backtrack(chooses) {
    if (chooses.length === track.length) {
      res.push(track.slice());
      return;
    }
    for (let i = 0; i < chooses.length; i++) {
      if (track.includes(chooses[i])) continue;
      // 作出选择
      track.push(chooses[i]);

      backtrack(chooses);

      // 所做的选择反悔
      track.pop();
    }
  }
  backtrack(nums);
  return res;
};
// @lc code=end

/*
 * @lc app=leetcode.cn id=77 lang=javascript
 *
 * [77] 组合
 */

// @lc code=start
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  let res = [];
  let track = [];
  function backtrack(start) {
    if (track.length === k) {
      res.push(track.slice());
      return;
    }

    for (let i = start; i <= n; i++) {
      track.push(i);
      backtrack(i + 1);
      track.pop();
    }
  }
  backtrack(1);
  return res;
};
// @lc code=end

/*
 * @lc app=leetcode.cn id=78 lang=javascript
 *
 * [78] 子集
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  let res = [],
    track = [];
  function backtrack(nums, start) {
    res.push(track.slice());
    for (let i = start; i < nums.length; i++) {
      track.push(nums[i]);
      backtrack(nums, i + 1, track);
      track.pop();
    }
  }
  backtrack(nums, 0);
  return res;
};

// @lc code=end

/*
 * @lc app=leetcode.cn id=18 lang=javascript
 *
 * [18] 四数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
// 回溯算法, 疯狂减枝
var fourSum = function(nums, target) {
  let res = [];
  let track = [];
  nums.sort((a, b) => a - b);
  if (
    nums.length &&
    (nums[nums.length - 1] * 4 < target || nums[0] * 4 > target)
  ) {
    return [];
  }

  function backtrack(start = 0, Sum) {
    if (Sum === target && track.length === 4) {
      res.push(track.slice());
      return;
    }
    if (track.length > 4) return;
    for (let i = start; i < nums.length; i++) {
      if (nums.length - i < 4 - track.length) continue;
      if (i > start && nums[i] === nums[i - 1]) continue;
      if (
        i < nums.length - 1 &&
        Sum + nums[i] + (3 - track.length) * nums[i + 1] > target
      )
        continue;

      if (
        i < nums.length - 1 &&
        Sum + nums[i] + (3 - track.length) * nums[nums.length - 1] < target
      )
        continue;

      track.push(nums[i]);
      backtrack(i + 1, Sum + nums[i]);
      track.pop(nums[i]);
    }
  }
  backtrack(0, 0);
  return res;
};
// @lc code=end

// console.log(fourSum([1, 0, -1, 0, -2, 2], 0));

/*
 * @lc app=leetcode.cn id=22 lang=javascript
 *
 * [22] 括号生成
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  let track = [];
  let res = [];
  /**
   * leftNum 剩余左括号数量
   * rightNum 剩余右括号数量
   */
  function backtrack(leftNum, rightNum) {
    // 合格的括号对满足以下条件
    // 1. 任意字串[0,...,i]，左括号数量都大于右括号数量
    // 2. 对于所有合法的括号对，左括号数都等于右括号数

    // 剩余左括号数大于剩余右括号数，说明字串的左括号数小于右括号数，不符合条件
    if (leftNum > rightNum) return;
    // 剩余左括号数或者剩余右括号数不足，不符合条件
    if (leftNum < 0 || rightNum < 0) return;
    // 经过第一个判断，左括号数量肯定大于等于右括号数量，如果剩余左右括号数都为0，说明就是合格的括号对
    if (leftNum === 0 && rightNum === 0) {
      res.push(track.join(""));
      return;
    }

    // 做选择
    track.push("(");
    backtrack(leftNum - 1, rightNum);
    // 回溯
    track.pop();

    // 做选择
    track.push(")");
    backtrack(leftNum, rightNum - 1);
    // 回溯
    track.pop();
  }

  // 剩余左右括号数各给n个
  backtrack(n, n);
  return res;
};
// @lc code=end

/*
 * @lc app=leetcode.cn id=51 lang=javascript
 *
 * [51] N 皇后
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
  const getMatrix = (n, stuff = "") => {
    const res = [];
    for (let i = 0; i < n; i++) {
      const list = [];
      for (let j = 0; j < n; j++) {
        list.push(stuff);
      }
      res.push(list);
    }
    return res;
  };
  const res = [];
  const emptyBoard = getMatrix(n, ".");
  backtrack(emptyBoard, 0, res);
  return res;
};

function backtrack(matrix, row, res) {
  if (matrix.length === row) {
    res.push(matrix.map((item) => item.join("")));
    return;
  }

  const rowData = matrix[row];
  for (let col = 0; col < rowData.length; col++) {
    if (!isValid(matrix, row, col)) {
      continue;
    }
    rowData[col] = "Q";
    backtrack(matrix, row + 1, res);
    rowData[col] = ".";
  }
}

function isValid(matrix, row, col) {
  const size = matrix.length;
  for (let i = 0; i < size; i++) {
    if (
      matrix[i][col] === "Q" ||
      matrix[row][i] === "Q" ||
      matrix[i][row + col - i] === "Q" ||
      matrix[i][i + col - row] === "Q"
    )
      return false;
  }

  return true;
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=37 lang=javascript
 *
 * [37] 解数独
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
  const maxRow = 9,
    maxCol = 9;
  function isValid(i, j, ch) {
    for (let k = 0; k < 9; k++) {
      if (board[i][k] === ch) return false;
      if (board[k][j] === ch) return false;
      const chunkI = Math.floor(i / 3);
      const chunkJ = Math.floor(j / 3);
      const chunkIStart = chunkI * 3;
      const chunkJStart = chunkJ * 3;
      const iIndex = chunkIStart + Math.floor(k / 3);
      const jIndex = chunkJStart + (k % 3);
      if (board[iIndex][jIndex] === ch) return false;
    }
    return true;
  }

  function backtrack(i, j) {
    if (j === maxCol) {
      return backtrack(i + 1, 0);
    }
    if (i === maxRow) {
      return true;
    }

    if (board[i][j] !== ".") {
      return backtrack(i, j + 1);
    }

    for (let t = 1; t <= 9; t++) {
      const ch = String(t);
      if (!isValid(i, j, ch)) continue;
      board[i][j] = ch;

      if (backtrack(i, j + 1)) {
        return true;
      }
      board[i][j] = ".";
    }
    return false;
  }
  backtrack(0, 0);
};
// @lc code=end

let matrix = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"],
];
solveSudoku(matrix);
console.log(matrix);

/*
 * @lc app=leetcode.cn id=494 lang=javascript
 *
 * [494] 目标和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function(nums, S) {
  let res = 0;
  let count = 0;
  function backtrack(i) {
    if (i === nums.length) {
      if (res === S) {
        count++;
      }
      return;
    }
    res += nums[i];
    backtrack(i + 1);
    res -= nums[i];

    res -= nums[i];
    backtrack(i + 1);
    res += nums[i];
  }
  backtrack(0);
  return count;
};
// @lc code=end

void traverse(TreeNode root) {
    // 前序遍历代码
    traverse(root.left);
    // 中序遍历代码
    traverse(root.right);
    // 后序遍历代码
}

void traverse(ListNode root) {
    for(child of root.children){
        // 前序遍历代码
    traverse(child);
    // 后序遍历代码
    }
}

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target)
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

void traverse(ListNode head) {
    // 前序遍历代码
    traverse(head.next);
    // 后序遍历代码
}

const DRAFT_STATE = Symbol("immer-draft-state");

const isDraft = (value) => !!value && !!value[DRAFT_STATE];
const isDraftable = (value) => value !== null && typeof value === "object";
const has = (obj, prop) => Object.prototype.hasOwnProperty.call(obj, prop);
const shallowCopy = (value) =>
  Array.isArray(value) ? [...value] : { ...value };

function createDraft(parent, base, proxies) {
  const state = {
    finalized: false,
    parent,
    base,
    copy: undefined,
    drafts: {},
  };
  const p = Proxy.revocable(state, {
    get(state, prop) {
      if (prop === DRAFT_STATE) return state;
      if (state.copy) {
        const value = state.copy[prop];
        if (value === state.base[prop] && isDraftable(value)) {
          return (state.copy[prop] = createDraft(state, value, proxies));
        }
        return value;
      }
      if (has(state.drafts, prop)) return state.drafts[prop];
      const value = state.base[prop];
      if (!isDraft(state) && isDraftable(value)) {
        return (state.drafts[prop] = createDraft(state, value, proxies));
      }
      return value;
    },
    has(state, prop) {
      return Reflect.has(state.copy || state.base, prop);
    },
    ownKeys(state) {
      return Reflect.ownKeys(state.copy || state.base);
    },
    set(state, prop, value) {
      if (!state.copy) {
        if (
          (has(state.base, prop) && state.base[prop] === value) ||
          (has(state.drafts, prop) && state.drafts[prop] === value)
        )
          return true;
        markChanged(state);
      }
      state.copy[prop] = value;
      return true;
    },
    deleteProperty(state, prop) {
      markChanged(state);
      delete state.copy[prop];
      return true;
    },
    getOwnPropertyDescriptor(state, prop) {
      const owner =
        state.copy || has(state.drafts, prop) ? state.drafts : state.base;
      return Reflect.getOwnPropertyDescriptor(owner, prop);
    },
  });
  proxies.push(p);
  return p.proxy;
}

function markChanged(state) {
  if (!state.copy) {
    state.copy = shallowCopy(state.base);
    Object.assign(state.copy, state.drafts); // works on Array
    if (state.parent) markChanged(state.parent);
  }
}

function finalize(draft) {
  if (isDraft(draft)) {
    const state = draft[DRAFT_STATE];
    const { copy, base } = state;
    if (copy) {
      if (state.finalized) return copy; // TEST: self reference
      state.finalized = true;
      Object.entries(copy).forEach(([prop, value]) => {
        // works on Array
        if (value !== base[prop]) copy[prop] = finalize(value);
      });
      return copy;
    }
    return base;
  }
  return draft;
}

function createImmer(base) {
  const proxies = [];
  const draft = createDraft(undefined, base, proxies);
  const finish = () => {
    const res = finalize(draft);
    proxies.forEach((p) => p.revoke());
    return res;
  };
  return { draft, finish };
}

function produce(base, producer) {
  if (typeof base === "function" && producer !== "function") {
    return function (s = producer, ...args) {
      // TEST: produce as object method
      return produce(s, (draft) => base.call(this, draft, ...args));
    };
  }
  const { draft, finish } = createImmer(base);
  const p = producer.call(draft, draft);
  if (p instanceof Promise) return p.then(() => finish());
  return finish();
}

const baseState = [
  {
    todo: "Learn typescript",
    done: true,
  },
  {
    todo: "Try immer",
    done: false,
  },
];
const nextState = produce(baseState, (draftState) => {
  draftState.push({ todo: "Tweet about it", done: false });
  draftState[1].done = true;
});
console.log(baseState, nextState);