小小贪吃蛇，移动花样多。
平移加旋转，为把迷宫破。
代码复代码，bug 何其多。
六步化一步，AC 定我夺。
—— 1210. 穿过迷宫的最少移动次数

一、网格图 DFS

适用于需要计算连通块个数、大小的题目。

部分题目做法不止一种，也可以用 BFS 或并查集解决。

二叉树 DFS 与网格图 DFS 的区别：

	二叉树	网格图
递归入口	根节点	网格图的某个格子
递归方向	左儿子和右儿子	一般为左右上下的相邻格子
递归边界	空节点（或者叶节点）	出界、遇到障碍或者已访问

• 200. 岛屿数量
• 695. 岛屿的最大面积
• 3619. 总价值可以被 K 整除的岛屿数目 1461
• 面试题 16.19. 水域大小
• LCS 03. 主题空间
• 463. 岛屿的周长
• 2658. 网格图中鱼的最大数目 1490
• 733. 图像渲染
• 1034. 边界着色 1579
• 1020. 飞地的数量 1615
• 2684. 矩阵中移动的最大次数 1626
• 1254. 统计封闭岛屿的数目 1659
• 130. 被围绕的区域
• 1905. 统计子岛屿 1679
• 1391. 检查网格中是否存在有效路径 1746
• 417. 太平洋大西洋水流问题
• 529. 扫雷游戏
• 1559. 二维网格图中探测环 1838
• 827. 最大人工岛 1934 我的题解有变形题
• LCP 63. 弹珠游戏 也可以不用 DFS
• 305. 岛屿数量 II（会员题）
• 2061. 扫地机器人清扫过的空间个数（会员题）也可以迭代
• 2852. 所有单元格的远离程度之和（会员题）
• 489. 扫地机器人（会员题）

二、网格图 BFS

适用于需要计算最短距离（最短路）的题目。

DFS 是不撞南墙不回头；BFS 是先访问近的，再访问远的。

• 1926. 迷宫中离入口最近的出口 1638
• 1091. 二进制矩阵中的最短路径 1658
• 1162. 地图分析 1666
• 542. 01 矩阵
• 994. 腐烂的橘子
• 1765. 地图中的最高点 1783
• 934. 最短的桥 1826
• 2146. 价格范围内最高排名的 K 样物品 1837
• 1293. 网格中的最短路径 1967
• 909. 蛇梯棋 2020
• 1210. 穿过迷宫的最少移动次数 2022
• 675. 为高尔夫比赛砍树
• 2812. 找出最安全路径 2154
• 749. 隔离病毒 2277
• 1730. 获取食物的最短路径（会员题）
• 286. 墙与门（会员题）
• 490. 迷宫（会员题）
• 505. 迷宫 II（会员题）
• 499. 迷宫 III（会员题）
• 317. 离建筑物最近的距离（会员题）
• 2814. 避免淹死并到达目的地的最短时间（会员题）

三、网格图 0-1 BFS

边权只有 $0$ 和 $1$ 的题目，也可以用 BFS 做。

• 3286. 穿越网格图的安全路径 做到 $\mathcal{O}(mn)$
• 2290. 到达角落需要移除障碍物的最小数目 2138
• 1368. 使网格图至少有一条有效路径的最小代价 2069
• 3552. 网格传送门旅游 2036
• 1824. 最少侧跳次数
• LCP 56. 信物传送

四、网格图 Dijkstra

见 图论题单 中的 Dijkstra。

五、综合应用

• 1631. 最小体力消耗路径 1948
• 778. 水位上升的泳池中游泳 2097
• 329. 矩阵中的最长递增路径
• 3568. 清理教室的最少移动 2143 状压 BFS（分层图最短路）
• 1036. 逃离大迷宫 2165
• 864. 获取所有钥匙的最短路径 2259 状压 BFS（分层图最短路）
• 1263. 推箱子 2297
• 2258. 逃离火灾 2347
• 2556. 二进制矩阵中翻转最多一次使路径不连通 2369
• 2577. 在网格图中访问一个格子的最少时间 2382
• 2617. 网格图中最少访问的格子数 2582
• LCP 13. 寻宝 状压 DP
• LCP 31. 变换的迷宫
• LCP 45. 自行车炫技赛场
• LCP 75. 传送卷轴
• 1778. 未知网格中的最短路径（会员题）
• 694. 不同岛屿的数量（会员题）
• 711. 不同岛屿的数量 II（会员题）
• 1102. 得分最高的路径（会员题）

思考题

1. 对于 $m$ 行 $n$ 列的网格图，BFS 的队列最多消耗多少空间？DFS 的递归栈最多消耗多少空间？
2. 构造一个网格图，让 DFS 的递归深度尽量大。如果起点是 $(0,0)$ 要如何构造？如果起点是 $(i,j)$ 要如何构造？

欢迎在评论区发表你的思路。

算法题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

如果你发现有题目可以补充进来，欢迎评论反馈。