你好！作为金牌教练，我们今天继续深入网格图搜索的专项训练。

前两课我们学习了“统计岛屿数量”和“判断岛屿是否封闭”。今天这道题**“飞地的数量”在逻辑上与“封闭岛屿”高度相似，但考察点更侧重于“连通块内部属性的累加统计”**。

一、 题目描述：飞地的数量 (Number of Enclaves)

题目背景： 在领土划分中，我们需要计算那些被敌方完全包围、无法撤回国境线（网格边缘）的士兵人数。

任务描述： 给你一个大小为 $M \times N$ 的二维网格 grid，其中：

• 1 表示陆地（士兵）。
• 0 表示水域。 飞地 是指不在网格边界上，并且无法通过上下左右相邻的陆地单元格到达网格边界的陆地单元格。 请计算网格中所有飞地单元格的数量。

输入格式： 第一行包含两个整数 $M$ 和 $N$，$1 \le M, N \le 500$。 接下来的 $M$ 行，每行包含 $N$ 个用空格分隔的整数（0 或 1）。

输出格式： 输出一个整数，表示飞地单元格的总数。

样例 1：

输入：

4 4
0 0 0 0
1 0 1 0
0 1 1 0
0 0 0 0

输出：

3

样例说明：有三个 1 被 0 包围，且无法到达边界。

样例 2：

输入：

4 4
0 1 1 0
0 0 1 0
0 0 1 0
0 0 0 0

输出：

0

样例说明：所有的 1 都在边界上，或与边界上的 1 相连，因此没有飞地。

二、 预备知识点

1. 图的遍历 (DFS/BFS)： 核心搜索工具。
2. 正难则反 (Complementary Thinking)： 在 NOI 中，如果直接找“无法到达边界的点”比较困难，我们可以先找“所有能到达边界的点”。
3. 网格坐标压缩/解压： 虽然本题不需要，但当 $M, N$ 极大时需考虑。
4. 全局状态统计： 在搜索过程中或结束后进行像素级的计数。

三-1. 启发式引导：草稿纸上的推演过程

请在草稿纸上画一个 $4 \times 4$ 的矩阵，手动模拟以下过程：

1. 确定目标： 我们要的是那些“被困住”的 1。
2. 标记边缘： 观察第一行、最后一行、第一列、最后一列。如果这些地方有 1，它们肯定不是飞地。
3. 连锁反应（重点）：
   • 如果边缘有一个 1，那么所有与之相连的 1 都能逃生。
   • 拿笔把这些“能逃生”的 1 全部涂成 0（或者标记为已访问）。
4. 最后收网： 剩下的 1 就是无路可逃的士兵。数一数剩下多少个 1。

三-2. 复杂度思考

• 时间复杂度：
  • 第一遍搜索（处理边缘）：$O(M \times N)$。
  • 第二遍扫描（统计余量）：$O(M \times N)$。
  • 总计 $O(M \times N)$。对于 $500 \times 500 = 2.5 \times 10^5$ 的规模，C++ 可以在 10ms 内解决。
• 空间复杂度：
  • 主要是递归深度。最坏情况（蛇形长蛇）为 $O(M \times N)$。

四、 算法流程图 (Mermaid 风格)

我们采用“边缘渗透法”来规避复杂的中间逻辑：

graph TD
    Start("开始程序") --> Input("读取 M, N 和网格数据")
    Input --> ProcessEdge("处理四条边界")
    
    ProcessEdge --> EdgeLoop("遍历边界上的单元格")
    EdgeLoop --> IsLand{"该点是 1 吗?"}
    
    IsLand -- "是" --> DFS("从该点启动 DFS 渗透")
    DFS --> FillZero("将当前格及相连的 1 全部置为 0")
    FillZero --> DFSExit("渗透结束")
    
    IsLand -- "否" --> NextEdge("检查下一个边界点")
    DFSExit --> NextEdge
    
    NextEdge --> EdgeAllDone{"边界处理完了吗?"}
    
    EdgeAllDone -- "是" --> FinalCount("遍历整个网格统计剩下的 1")
    FinalCount --> Counter("ans += grid_i_j")
    Counter --> Result("输出 ans")
    
    Result --> End("结束")

五、 读题理解关键词

在 NOI 赛场上，看到这类题要迅速定位以下信息：

1. “数量” (Count)：
   • 注意！前一题“封闭岛屿”问的是有几个连通块。
   • 本题问的是有几个单元格。
   • 策略调整： 即使两个飞地陆地相连，也要按格数分别计算，而不是计为 1 个。
2. “无法到达边界”：
   • 标准解法是“从边界向内搜”。
   • 这种思路叫**“边界驱动的搜索”**。
3. 数据规模 (500)：
   • $500^2$ 的规模对递归栈有一定要求。
   • NOI 建议： 在 Linux 环境评测时，由于 ulimit -s 的限制，如果递归太深可能爆栈。建议在练习时也尝试用 BFS（队列）实现，提高鲁棒性。

六、 复杂度优化建议

1. 原地修改： 为了节省空间，直接将能逃生的 1 修改为 0，不需要额外的 vis 数组。
2. 减少检查次数： 处理四条边时，四个角不要重复搜索。
3. 快读优化： 虽然 $2.5 \times 10^5$ 规模不大，但养成 scanf 或 cin.tie(0) 的习惯，能让你在更难的题（如 $10^6$ 规模）中占得先机。

教练点评： “飞地的数量”和“岛屿数量”的区别在于统计对象。前者统计的是“像素”，后者统计的是“集合”。理解了这一点，你对 DFS 的应用就从“点”升华到了“面”！加油！