走迷宫算法

## 前置通用准备
### 1. 迷宫规范
- 迷宫为 **网格型**（墙是黑色方块，通路是白色），墙/通路格子统一为 `20x20像素`
- 角色移动步长固定为 **20步**（刚好走一格），迷宫四周必须有围墙，防止角色走出舞台
- 起点：舞台任意白色格子（比如x=-200,y=100）；终点：舞台另一处白色格子（比如x=200,y=-100）

### 2. 角色与画笔设置
1. 角色：选默认的「小方块」即可（圆形也可以），**必须把角色的中心点对准正中心**（否则移动错位）
2. 画笔初始化通用规则：
   - 抬笔、清空舞台画笔痕迹、设置画笔粗细为2（看得清路径）
   - 角色移到「起点坐标」，落笔准备绘制路径

### 3. 关键变量（两套程序会单独创建自己的变量，互不影响）
- 所有变量设为「适用于当前角色」
- 核心通用变量：`当前x坐标`、`当前y坐标`、`是否找到终点`（布尔值，默认false）
---
# ✍️ 第一套：DFS深度优先算法 自动走迷宫（完整独立程序）
## ✅ 核心逻辑【重中之重】
DFS的核心是：**「一路走到黑，碰壁则回溯」，深度优先，递归探索**
1. 从起点出发，选择一个方向（上/下/左/右）一直往前走，直到遇到「墙/边界/已经走过的路」（碰壁）
2. 碰壁后，**回退到上一个路口**，换另一个未探索的方向继续走
3. 用画笔实现可视化：**蓝色 = 前进探索路径**、**红色 = 回溯死路路径**（你之前提到的泛红效果，就是DFS的回溯染红）
4. 找到终点后，立刻停止所有探索，保留最终正确路径
5. DFS的核心依赖：**Scratch的【递归自定义积木】** ，这是DFS在Scratch中实现的唯一核心方式！

## ✅ 完整积木脚本（分3部分，顺序执行，全复制即可）
### 【第一部分】初始化脚本（绿旗被点击，主程序入口）
```
当绿旗被点击
  清空所有画笔
  全部停止
  将笔的颜色设为蓝色 // 前进路径-蓝色
  将笔的粗细设为2
  设 [是否找到终点 v] 为 假
  设 [已走过的路径 v] 为 空列表 // 记录走过的坐标，防止重复走
  移到 x: [起点x] y: [起点y] // 替换成你的迷宫起点坐标，比如x=-200,y=100
  抬笔
  调用 【DFS递归探索 (x) (y)】 // 传入起点坐标，启动DFS核心
```

### 【第二部分】核心：DFS递归自定义积木（最关键！必做）
> 新建自定义积木，命名为「DFS递归探索 (x坐标) (y坐标)」，**勾选「运行时不刷新屏幕」**（防止角色闪烁，必须勾）
```
定义 DFS递归探索 (当前x) (当前y)
  如果 <(是否找到终点) = 真> 那么 // 找到终点，直接退出所有递归，终止探索
    停止 [这个脚本 v]
  结束
  // 边界判断：当前坐标是墙/出舞台/已走过 → 是死路，直接返回上一步
  如果 <<<碰到黑色?>::侦测> 或 <(当前x) < -240>> 或 <(当前x) > 240>> 或 <(当前y) < -180>> 或 <(当前y) > 180>> 或 <(已走过的路径) 包含 (连接 (当前x) 和 (连接 [,] 和 (当前y)))>> 那么
    停止 [这个脚本 v]
  结束
  // 合法位置：走到当前坐标，记录路径+画笔绘制前进路线
  移到 x: (当前x) y: (当前y)
  落笔
  等待 0.05 秒 // 调速，可删
  将 (连接 (当前x) 和 (连接 [,] 和 (当前y))) 添加到 [已走过的路径 v]
  
  // 判断：是否到达终点？
  如果 <碰到 [红色]?>::侦测 // 建议把终点格子涂成红色，方便判断
    设 [是否找到终点] 为 真
    说 [找到终点啦！] 2 秒
    停止 [全部 v]
  结束
  
  // 核心DFS：按「上→右→下→左」顺序递归探索（顺序可换，不影响算法），一路走到黑
  DFS递归探索 (当前x) (当前y + 20) // 向上走一格
  DFS递归探索 (当前x + 20) (当前y) // 向右走一格
  DFS递归探索 (当前x) (当前y - 20) // 向下走一格
  DFS递归探索 (当前x - 20) (当前y) // 向左走一格
  
  // 回溯核心：四个方向都走完了，是死路！泛红标记+回退
  如果 <(是否找到终点) = 假> 那么
    将笔的颜色设为红色 // 泛红算法核心：死路用红色画笔标记
    移到 x: (当前x) y: (当前y)
    等待 0.05 秒
    将笔的颜色设为蓝色 // 恢复蓝色，方便后续探索
  结束
  抬笔
```

### ✅ DFS算法特点总结
1. 优点：逻辑简单、代码少、Scratch中极易实现，泛红回溯可视化效果极佳
2. 缺点：会走「死胡同」，路径不是最短路径，是「先探索到底再回头」的暴力探索路径
3. 核心标识：**蓝色前进，红色回溯染红死路**，路径会有红色的死路痕迹，最终蓝色路径为正确路线

---
# ✍️ 第二套：泛洪算法(Flood Fill 洪水填充) 自动走迷宫（完整独立程序，纯算法无DFS）
## ✅ 核心逻辑【重中之重，和DFS完全不同，必看】
> 泛洪算法 也叫**洪水填充算法**，是你要求的纯独立算法，和DFS没有任何关系！！！
### 核心原理
泛洪的核心是：**「洪水漫灌式扩散」，广度优先探索，层层向外蔓延**，像水从起点流出来一样，均匀铺满所有能走到的通路，直到水流碰到终点为止。
1. 从起点出发，**同时向所有方向（上/下/左/右）扩散探索**，不是「一路走到黑」，而是「一格一格向外铺」
2. 探索过的路径会被标记，**绝对不会走回头路、不会走死胡同**，因为是「先铺所有可能的路，再找终点」
3. 泛洪算法的核心依赖：**「队列」思想**（先进先出），而不是DFS的「递归」！这是和DFS最本质的区别
4. 画笔可视化：统一用 **绿色** 绘制路径（和DFS区分），全程无回溯、无红色死路，因为泛洪不会走死路！
5. 泛洪算法的最大优势：**自动找到迷宫的「最短路径」**，这是DFS完全做不到的！

### ✅ 核心知识点（Scratch实现泛洪的关键）
Scratch中没有「队列」这个数据结构，我们用 **两个列表** 模拟队列，存储「待探索的坐标」，这是泛洪算法在Scratch中实现的唯一核心方式：
1. 列表「待探索x坐标」：存储队列中所有待探索格子的x值
2. 列表「待探索y坐标」：存储队列中所有待探索格子的y值
3. 列表「已探索路径」：存储已经走过的坐标，防止重复探索（防转圈）

## ✅ 完整积木脚本（分3部分，纯泛洪、无递归、无DFS，完全独立，全复制即可）
### 【第一部分】初始化脚本（绿旗被点击，主程序入口）
```
当绿旗被点击
  清空所有画笔
  全部停止
  将笔的颜色设为绿色 // 泛洪路径统一用绿色，和DFS区分
  将笔的粗细设为2
  设 [是否找到终点 v] 为 假
  // 清空所有列表，初始化队列
  删除 [全部 v] 项 of [待探索x坐标 v]
  删除 [全部 v] 项 of [待探索y坐标 v]
  删除 [全部 v] 项 of [已探索路径 v]
  // 移到起点，把起点坐标加入队列（泛洪的第一步：洪水从起点开始流）
  移到 x: [起点x] y: [起点y] // 替换成你的迷宫起点坐标，和DFS一致即可
  将 (起点x) 添加到 [待探索x坐标 v]
  将 (起点y) 添加到 [待探索y坐标 v]
  将 (连接 (起点x) 和 (连接 [,] 和 (起点y))) 添加到 [已探索路径 v]
  抬笔
```

### 【第二部分】核心：泛洪算法主循环（无递归！纯循环，泛洪的灵魂）
> 这个脚本是**独立的绿旗脚本**，和上面的初始化脚本一起运行，是泛洪的核心，没有递归积木！
```
当绿旗被点击
  重复执行直到 <(是否找到终点) = 真> 或 <(长度 of [待探索x坐标 v]) = 0>
    // 队列空了=迷宫无通路，退出
    如果 <(长度 of [待探索x坐标 v]) = 0> 那么
      说 [迷宫无解！] 2 秒
      停止 [全部 v]
    结束
    // 队列的核心规则：先进先出 → 取出队列第一个坐标，作为当前探索点
    设 [当前x v] 为 (第 1 项 of [待探索x坐标 v])
    设 [当前y v] 为 (第 1 项 of [待探索y坐标 v])
    // 取出后删除，队列变短，保证下一次取新的坐标
    删除第 1 项 of [待探索x坐标 v]
    删除第 1 项 of [待探索y坐标 v]
    
    // 走到当前坐标，画笔绘制路径
    移到 x: (当前x) y: (当前y)
    落笔
    等待 0.05 秒 // 调速，可删
    
    // 判断：是否到达终点？
    如果 <碰到 [红色]?>::侦测 // 终点还是涂成红色，和DFS一致
      设 [是否找到终点] 为 真
      说 [找到终点！最短路径✅] 2 秒
      停止 [全部 v]
    结束
    
    // 核心泛洪：向四个方向「漫灌」，把合法的新坐标加入队列
    调用 【泛洪探索方向 (当前x) (当前y + 20)】 // 向上探索
    调用 【泛洪探索方向 (当前x + 20) (当前y)】 // 向右探索
    调用 【泛洪探索方向 (当前x) (当前y - 20)】 // 向下探索
    调用 【泛洪探索方向 (当前x - 20) (当前y)】 // 向左探索
    抬笔
  结束
```

### 【第三部分】辅助自定义积木：泛洪探索单个方向（判断坐标合法性）
> 新建自定义积木，命名为「泛洪探索方向 (目标x) (目标y)」，无需勾选任何选项
```
定义 泛洪探索方向 (目标x) (目标y)
  // 判断规则：目标坐标不是墙、不出舞台、没被探索过 → 合法
  如果 <<<碰到黑色? 在 x: (目标x) y: (目标y)>::侦测 = 假> 且 <(目标x) > -240> 且 <(目标x) < 240> 且 <(目标y) > -180> 且 <(目标y) < 180>> 那么
    设 [坐标字符串 v] 为 (连接 (目标x) 和 (连接 [,] 和 (目标y)))
    如果 <(已探索路径) 不包含 (坐标字符串)> 那么
      // 合法坐标：加入队列+标记已探索，等待后续漫灌
      将 (目标x) 添加到 [待探索x坐标 v]
      将 (目标y) 添加到 [待探索y坐标 v]
      将 (坐标字符串) 添加到 [已探索路径 v]
    结束
  结束
```

### ✅ 泛洪算法特点总结
1. 优点：**绝对不会走死路、不会回溯**，自动找到迷宫「最短路径」，路径干净无冗余，可视化效果清爽（只有绿色路径）
2. 缺点：代码比DFS稍多，需要用列表模拟队列，但逻辑非常清晰
3. 核心标识：**全程绿色路径**，无红色痕迹，路径是最短的最优解
4. 核心区别：无递归、无回溯、无泛红，纯「漫灌式」探索

---
# ✨ 重中之重：DFS算法 vs 泛洪算法 核心区别（两套程序的本质差异）
## 你一定要知道的关键对比，完美回答你的需求
| 对比维度 | DFS深度优先算法 | 泛洪(Flood Fill)算法 |
|----------|----------------|----------------------|
| 核心思想 | 深度优先、一路走到黑、递归回溯 | 广度优先、洪水漫灌、队列扩散 |
| 实现方式 | 依赖【递归自定义积木】 | 依赖【列表模拟队列】+纯循环，无递归 |
| 路径特点 | 会走死胡同，路径不是最短，有冗余 | 绝对不走死胡同，**必出最短路径** |
| 可视化效果 | 蓝色前进+红色泛红回溯死路 | 只有绿色路径，干净无冗余 |
| 探索逻辑 | 一条路走到头再回头换方向 | 同时向所有方向扩散，层层探索 |
| 核心优势 | 代码简单、易实现、泛红效果直观 | 最优解、最短路径、无无效探索 |

---
## ✅ 最后补充（实操避坑，必看）
1. 终点标记：建议把迷宫终点的格子用「红色」填充，两套程序都用`碰到红色？`判断终点，非常方便。
2. 速度调节：两个程序里的`等待0.05秒`都是调速用的，想快就删，想慢就改大数值（比如0.1）。
3. 迷宫适配：两套程序都适配任意20x20网格迷宫，只需修改「起点坐标」即可，无需改其他逻辑。
4. 互不干扰：两套程序的变量、列表、画笔颜色都完全独立，你可以在Scratch中新建两个角色，一个放DFS脚本，一个放泛洪脚本，一键切换运行。

两套程序都是完整的、可直接运行的，你只需要复制积木、设置起点终点，就能看到DFS的「泛红回溯」和泛洪的「最短路径」两种不同的自动走迷宫效果啦！🎉