DFS + visited 集合

小明站在一个无限大的坐标系上（比如从 (0, 0) 开始），每走一步可以：

向 左（x - 1）

向 右（x + 1）

向 上（y + 1）

但有两个限制：

不能往下走 ❌

不能走到以前去过的地方 ❌（每个格子只能走一次）

问：走 n 步，有多少种不同的走法？

✅ 举个例子来说明： 从 (0, 0) 出发

当 n = 1： 只走一步，有 3 种选择：

向右 → (1, 0)

向左 → (-1, 0)

向上 → (0, 1) 当 n = 2： 每一步都不能走重复点，比如：

第一步向右 (1,0)，第二步可以向右 (2,0)、左回去 (0,0)❌、上 (1,1)，但不能走 (0,0)，因为已经走过了

我们必须用遍历的方法去试一遍所有不重复的走法，这就是用“递归”做的。

✅ 怎么做：用“递归 + 回溯” 我们可以用一个函数 dfs(x, y, step) 来表示：

“现在在 (x,y) 这个位置，已经走了 step 步，看看接下来怎么走”

✅ 用 JavaScript 写的完整代码（有中文注释）：

function countWays(n) {
   const visited = new Set(); // 记录走过的点
   let count = 0; // 最后结果


   // 深度优先搜索
   function dfs(x, y, steps) {
       if (steps === n) { // 已经走完 n 步
           count++;
           return;
       }


       const key = `${x},${y}`;
       visited.add(key); // 当前点记为已访问


       // 三个方向：右、左、上
       const dirs = [
           [1, 0],  // 向右
           [-1, 0], // 向左
           [0, 1]   // 向上
       ];


       for (const [dx, dy] of dirs) {
           const nx = x + dx;
           const ny = y + dy;
           const nextKey = `${nx},${ny}`;


           // 没有访问过才能走
           if (!visited.has(nextKey)) {
               dfs(nx, ny, steps + 1); // 走一步
           }
       }


       visited.delete(key); // 回溯，把当前点从 visited 中移除
   }


   dfs(0, 0, 0); // 从 (0, 0) 开始走
   return count;
}

✅ 为什么用 Set 保存走过的点？ 因为不能走重复的点，比如：

走了 (0, 0) → (1, 0) → (0, 0) ← 这样是不合法的（回到了走过的点）

所以我们用 Set 存每次走过的位置，在走下一步前先检查它有没有在 Set 中。

✅ 回溯是什么意思？ 每次走一步之后，我们“试试看”，如果失败了（比如没法继续走），就“退回来”把这个点从 Set 中删掉（这叫“回溯”）。