你好！我是教练。经过前面几课的积累，你已经掌握了岛屿的“数量”、“面积”和“边界”处理。今天这道题 “子岛屿的数量” 是岛屿系列的集大成者，它考察的是两个图之间的拓扑包含关系。

在 NOI 竞赛中，这种“双图对比”的题型非常常见。它不仅要求你会搜索，还要求你具备 “预处理” 和 “逆向剔除” 的思维。

一、 题目描述：子岛屿的数量 (Count Sub Islands)

任务描述： 给定两个 $M \times N$ 的二进制矩阵 grid1 和 grid2。1 表示陆地，0 表示水域。 如果 grid2 中的一个岛屿（连通块），其所有单元格在 grid1 中对应的位置也都是陆地单元格，则称该岛屿为 grid1 的子岛屿。 请返回 grid2 中子岛屿的数量。

输入格式 (NOI 标准)： 第一行包含两个整数 $M, N$ ($1 \le M, N \le 500$)。 接下来 $M$ 行，每行 $N$ 个空格分隔的整数，表示 grid1。 接下来 $M$ 行，每行 $N$ 个空格分隔的整数，表示 grid2。

输出格式： 一个整数，表示子岛屿的数量。

样例 1 输入：

5 5
1 1 1 0 0
0 1 1 1 1
0 0 0 0 0
1 0 0 0 0
1 1 0 1 1
1 1 1 0 0
0 0 1 1 1
0 1 0 0 0
1 0 1 1 0
0 1 0 1 0

样例 1 输出：

3

样例 1 启发式解析（请在草稿纸上画出图层叠合）：

1. 岛屿 A (Grid2 左上角): 包含点 (0,0), (0,1), (0,2)。对比 Grid1，这三个点全是陆地。它是子岛屿。
2. 岛屿 B (Grid2 中右侧): 包含点 (1,2), (1,3), (1,4)。对比 Grid1，这三个点全是陆地。它是子岛屿。
3. 岛屿 C (Grid2 中间): 包含点 (2,1)。对比 Grid1，对应位置是水域。它不是子岛屿。
4. 岛屿 D (Grid2 左下角): 包含点 (3,0), (4,1)。对比 Grid1，这两点全是陆地。它是子岛屿。
5. 岛屿 E (Grid2 右下角): 包含点 (3,2), (3,3), (4,3)。对比 Grid1，(3,2) 和 (3,3) 对应位置是水域。它不是子岛屿。

二、 预备知识点

1. 洪水填充算法 (Flood Fill): 使用 DFS 或 BFS 遍历连通块。
2. 全称命题判定: 理解“子岛屿”要求每一个点都必须满足条件，即“只要有一个点不符，整块排除”。
3. 图层覆盖思维: 将两张地图重叠，寻找 grid2 的 1 落在 grid1 的 0 上的情况。

三、 启发式引导：草稿纸上的推理过程

请跟教练一起在纸上写下这两步：

1. 核心逻辑：寻找“害群之马”

• 如果 grid2 的某处是陆地，而 grid1 对应位置是水，这个点就是“害群之马”。
• 包含“害群之马”的 grid2 岛屿，整个都要被从答案候选名单中划掉。

2. 算法步骤（逆向剔除法）：

1. 第一遍扫描: 遍历 grid2。如果发现一个点 grid2[i][j] == 1 且 grid1[i][j] == 0，说明它所在的岛屿不可能是子岛屿。
2. 立即处理: 以此点为起点，在 grid2 上做一次搜索（DFS/BFS），把这个“坏岛屿”全部染成 0。
3. 第二遍扫描: 剩下的 grid2 陆地全都是“乖孩子”（完全被 grid1 覆盖）。现在只需按最基础的“岛屿数量”题目，统计 grid2 还剩多少个连通块即可。

3. 复杂度分析思考：

• 时间复杂度: $O(M \times N)$。虽然扫了两遍，但每个格子最多进出搜索队列/栈常数次。
• 空间复杂度: $O(M \times N)$。考虑到 $500 \times 500$ 且可能存在极端蛇形路径，请注意递归栈深度或改用 BFS。

四、 算法流程图 (Mermaid)

graph TD
    Start("开始") --> Loop1("步骤 1: 扫描 Grid2 寻找'坏点'")
    Loop1 --> CheckBad{"Grid2 为 1 且 Grid1 为 0?"}
    
    CheckBad -- "是" --> DFS1("DFS/BFS 淹没 Grid2 中整个连通块")
    DFS1 --> Next1("检查下一个点")
    CheckBad -- "否" --> Next1
    
    Next1 --> EndLoop1{"步骤 1 遍历结束?"}
    EndLoop1 -- "否" --> Loop1
    
    EndLoop1 -- "是" --> Loop2("步骤 2: 统计 Grid2 剩余岛屿数")
    Loop2 --> CheckLand{"Grid2 仍为 1?"}
    
    CheckLand -- "是" --> AddAns("答案 ans 加 1")
    AddAns --> DFS2("DFS/BFS 淹没该连通块")
    DFS2 --> Next2("检查下一个点")
    
    CheckLand -- "否" --> Next2
    Next2 --> EndLoop2{"全部遍历结束?"}
    EndLoop2 -- "是" --> Output("输出 ans")

五、 读题理解关键词

在 NOI 竞赛中，这些词是解题的信号灯：

1. “所有单元格” (Every cell):
   • 信号： 只要发现一个反例，整个集合就作废。
   • 策略： 先排除反例所在的集合，剩下的就是答案。
2. “子岛屿” (Sub-island):
   • 信号： 涉及到两个图层之间的空间包含关系。
   • 策略： 叠加比对。
3. 数据范围 (500):
   • 信号： $N \times M = 250,000$。
   • 策略： $O(NM)$ 算法首选。注意栈空间限制，如果 OJ 栈空间小，建议使用 queue 实现 BFS。

在 NOI 竞赛中，通过关键词快速定位算法：

1. “所有单元格” (Every cell)： 这是一个典型的全集约束。在处理全集约束时，“剔除不满足条件的子集”通常比“验证每一个子集”要高效得多。
2. “两个矩阵”： 提示我们要进行图层叠加思考。
3. “岛屿的数目”： 回归到最基础的连通块计数。

六、 时间复杂度优化建议

1. 合并步骤： 实际上不需要两遍完整的全图扫描。可以在一次扫描中完成：当你发现一个 grid2 的岛屿时，在搜索它的过程中记录它是否包含了“污染点”。如果整个搜索过程中都没遇到污染点，则 ans++。
2. I/O 优化： 对于 500x500 的双矩阵，数据量不小。在 C++ 中建议使用 scanf 或 cin.tie(NULL) 提高效率。
3. 空间防御： 鉴于 $500 \times 500$ 的规模，递归深度可能达到 $2.5 \times 10^5$。在 Linux 环境评测时请注意栈空间，或者直接使用 BFS 或 并查集。
4. 位运算（进阶）： 如果内存极度受限，可以将两个矩阵压缩进位。

教练点评： 这道题展示了如何将一个“复合判定问题”转化为两个“简单搜索问题”。在 NOI 赛场上，先简化模型、再编写代码，比直接上手写复杂的逻辑判断要稳健得多！

“子岛屿”问题本质上是带条件的连通块统计。掌握了“剔除法”，你就掌握了处理复杂包含关系的一把钥匙。这不仅是搜索，更是对题意进行“降维打击”的思维体现。加油！