小小贪吃蛇，移动花样多。
平移加旋转，为把迷宫破。
代码复代码，bug 何其多。
六步化一步，AC 定我夺。
—— 1210. 穿过迷宫的最少移动次数
一、网格图 DFS
适用于需要计算连通块个数、大小的题目。
部分题目也可以用 BFS 或并查集解决。
- 200. 岛屿数量
- 695. 岛屿的最大面积
- 面试题 16.19. 水域大小
- LCS 03. 主题空间
- 463. 岛屿的周长
- 2658. 网格图中鱼的最大数目 1490
- 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
适用于需要计算最短距离（最短路）的题目。
- 1926. 迷宫中离入口最近的出口 1638
- 1091. 二进制矩阵中的最短路径 1658
- 1162. 地图分析 1666
- 542. 01 矩阵
- 994. 腐烂的橘子
- 1765. 地图中的最高点 1783
- 934. 最短的桥 1826
- 2146. 价格范围内最高排名的 K 样物品 1837
- 1293. 网格中的最短路径 1967
- 909. 蛇梯棋 2020
- 1210. 穿过迷宫的最少移动次数 2022
- 675. 为高尔夫比赛砍树
- 749. 隔离病毒 2277
- 1730. 获取食物的最短路径（会员题）
- 286. 墙与门（会员题）
- 490. 迷宫（会员题）
- 505. 迷宫 II（会员题）
- 499. 迷宫 III（会员题）
- 317. 离建筑物最近的距离（会员题）
- 2814. 避免淹死并到达目的地的最短时间（会员题）
三、网格图 0-1 BFS
边权只有 0 和 1 的题目，也可以用 BFS 做。
- 3286. 穿越网格图的安全路径 做到 O(mn)
- 2290. 到达角落需要移除障碍物的最小数目 2138
- 1368. 使网格图至少有一条有效路径的最小代价 2069
- 3552. 网格传送门旅游 2036
- 1824. 最少侧跳次数
- LCP 56. 信物传送
四、网格图 Dijkstra
见 图论题单 中的 Dijkstra。
五、综合应用
- 1631. 最小体力消耗路径 1948
- 778. 水位上升的泳池中游泳 2097
- 329. 矩阵中的最长递增路径
- 1036. 逃离大迷宫 2165
- 3568. 清理教室的最少移动 ~2100 状压 BFS（分层图最短路）
- 864. 获取所有钥匙的最短路径 2259 状压 BFS（分层图最短路）
- 1263. 推箱子 2297
- 2258. 逃离火灾 2347
- 2556. 二进制矩阵中翻转最多一次使路径不连通 2369
- 2577. 在网格图中访问一个格子的最少时间 2382
- 2617. 网格图中最少访问的格子数 2582
- LCP 13. 寻宝 状压 DP
- LCP 31. 变换的迷宫
- LCP 45. 自行车炫技赛场
- LCP 75. 传送卷轴
- 694. 不同岛屿的数量（会员题）
- 711. 不同岛屿的数量 II（会员题）
- 1102. 得分最高的路径（会员题）
思考题
- 对于 m 行 n 列的网格图，BFS 的队列最多消耗多少空间？DFS 的递归栈最多消耗多少空间？
- 构造一个网格图，让 DFS 的递归深度尽量大。如果起点是 (0,0) 要如何构造？如果起点是 (i,j) 要如何构造？
欢迎在评论区发表你的思路。
算法题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分查找（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
如果你发现有题目可以补充进来，欢迎评论反馈。