P3702. 火星改造

解题思路

注意，本题和 腐烂的橘子 完全一致。

注意到本题的一个重要条件：该区域可能存在多个宜居区，即扩散过程可能有多个起点，故我们直接使用 多源 BFS 的模板即可完成本题目。

所谓 多源 BFS，无非是 BFS 的起点是多个起始位置，即我们的队列在初始化时，包含多个搜索起点。剩下的部分，则常规的 BFS 无异。

另外，由于需要判断是否能够将所有的 "NO" 拓展为 "YES"，我们只需要提前统计 "NO" 的个数 num_NO，在 BFS 过程每遇到一个 "NO" 就令数目减 1，在最后输出时判断 "NO" 的个数是否大于 0 即可。

思路展开 本题的扩散过程有多个起点：初始时可能存在多个 YES 宜居区，它们在同一个太阳日同时向外扩散，所以要用多源 BFS——把所有 YES 的坐标在一开始就全部放进队列，作为第 0 层。代码先双重遍历整个网格：遇到 YES 就入队并在 check_list 中标记已访问，遇到 NO 就把计数器 num_NO 加一。之后按层搜索：每一轮先取出当前队列长度 qSize，把这一层的点全部弹出，向上下左右四个方向尝试扩散；只有「不越界、未访问过、值为 NO」的格子才能入队，入队的同时标记已访问并把 num_NO 减一。变量 level 记录搜索层数，每处理完一层加一，正好对应一个太阳日。循环结束后，若 num_NO 仍大于 0，说明有 NO 格子永远无法被改造，输出 -1；否则输出 level-1，减一是因为最后一层出队时已经没有新格子入队，level 被多加了一次。

复杂度分析 设网格为 n 行 m 列。初始化时双重循环扫描全网格是 O(n*m)；BFS 过程中每个格子至多入队一次、出队一次，每次出队只检查 4 个方向，搜索部分也是 O(n*m)。总时间复杂度 O(n*m)，瓶颈就在这两次对全部格子的遍历。空间上，check_list 与网格同尺寸占 O(n*m)，队列最坏时可能容纳一整层的大量格子，上限同为 O(n*m)，故空间复杂度 O(n*m)。

边界与注意事项

• 输入行数不确定，代码用死循环配合空行与异常判断来结束读入，读到空行即停止。
• NA 格子既不入队也不计入 num_NO，天然起到障碍作用，BFS 不会穿过它。
• 若存在被 NA 完全围住的 NO 格子，BFS 结束后 num_NO 仍大于 0，正确输出 -1。
• 若网格里没有任何 NO 且至少有一个 YES，第一轮搜索只出队不进队，level 为 1，输出 level-1 即 0，表示不需要任何太阳日。
• 答案取 level-1 而不是 level：最后一层只出不进，层数被多计了一次；注释也提示可以把 level 初始化为 -1 来省去这次修正。