提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 算法1：统计所有元素均为 g 的倍数的子数组个数
- 思路
- 复杂度
- 算法2：扫雷风格——0/1矩阵中 1 标记为 9，0 输出周围 1 的个数
- 思路
- 复杂度
- 算法3：DFS 分割矩阵为两个和相等的连通区域
- 思路
- 复杂度
- 算法4：BFS多源扩展
- 思路
- 复杂度
- 小结：
算法1：统计所有元素均为 g 的倍数的子数组个数
思路
- 双指针（滑动窗口）：用
left和right维护当前窗口。 - 当
a[right]不是g的倍数时，窗口左端跳到上一个非法位置temp的右边，即left = temp + 1。 - 对于每个
right，合法窗口长度为len = right - left + 1，其中所有长度为 2 及以上的子数组数量为len - 1，累加到结果。 - 核心思想：不合法元素会切断窗口，将窗口切分成若干段，每段内所有元素都是 g 的倍数，因此，要对每段单独计数。
复杂度
- 时间：O(n)
- 空间：O(1)
算法2：扫雷风格——0/1矩阵中 1 标记为 9，0 输出周围 1 的个数
思路
- 直接暴力即可：遍历每个格子，如果是 1 直接输出
9；如果是 0，累加上、下、左、右、左上、右上、左下、右下共 8 个方向的数值。 - 代码中使用八个方向的邻居直接求和，矩阵下标从 1 开始，四周用 0 填充（默认值），避免边界判断。
复杂度
- 时间：O(n × m)
- 空间：O(n × m)
算法3：DFS 分割矩阵为两个和相等的连通区域
思路
- DFS 回溯 + 剪枝：
- 这一题要先计算矩阵总和
ans，若ans为奇数直接输出 0（不可能平分）。 - 从
(0,0)出发进行 DFS，count记录当前已选格子的累加和。 - 剪枝：若
count > ans/2，直接返回（已超一半）。 - 终止条件：
count == ans/2时，用当前格子数num更新最小值min。 - 每次向四个方向尝试，使用
flag[][]标记已访问，回溯时恢复状态。
- 这一题要先计算矩阵总和
- 这道是求包含起点的连通块，使其和恰好为总和的一半，且格子数最小。
复杂度
- 时间：指数级 O(4^(n×m))（剪枝后实际运行会好很多）
- 空间：O(n×m)（递归栈 + 标记数组）
算法4：BFS多源扩展
思路
- 多源BFS + 分层扩展：将所有初始的
'g'（草地）位置作为多个起点存入队列，然后进行 BFS 分层遍历，每层代表一秒的蔓延过程。 - 四方向扩散：每个
'g'向上下左右四个邻域格子扩散，若遇到'.'（空地）则将其变为'g'，并将新位置加入队列作为下一轮的扩散源点。 - 时间步控制：通过外层
while(k-->0)控制蔓延的轮数，每轮内先获取当前队列大小 ，即size，再对当前层的所有格子进行扩散，保证每个时间步只扩散一层（即每秒只蔓延一格距离）。 - 边界检查：通过
xx>=0 && xx<n && yy>=0 && yy<m，这样可以确保不越界。
大概这样是不会出错且不会漏项
复杂度
- 时间：O(n × m × k) —— 最坏的情况下每个格子可能被访问多次（k 轮每一轮都可能操作部分格子），不过，实际每个格子仅会在首次被变为
'g'时入队一次，因此实际有效操作次数为 O(n × m) - 空间：O(n × m) —— 存储网格
c[][]和队列（最坏情况下所有格子均为'g'入队）
小结：
四道算法题思路，第一个为python语法，剩余三个为Java语法
