在这道题中,我们需要解决一个关于火星区域大气改造的模拟问题。输入的区域由多个网格组成,每个网格的状态可以是以下三种之一:
YES
:表示该网格已完成大气改造,成为宜居区。NO
:表示该网格尚未改造,可以进行后续改造。NA
:表示死亡区,该区域不可穿越且不参与改造。我们的目标是判断在给定的初始网格状态下,所有的 NO
区域是否能够最终转变为 YES
区域。如果可以,输出完成改造所需的天数;如果无法完成,输出 -1
。
2XXX年,人类通过对火星的大气进行宜居改造分析,使得火星已在理论上具备人类宜居的条件;
由于技术原因,无法一次性将火星大气全部改造,只能通过局部处理形式;
假设将火星待改造的区域为 row * column的网格,每个网格有 3 个值,宜居区、可改造区、死亡区,使用 YES 、NO 、NA 代替,YES 表示该网格已经完成大气改造,NO 表示该网格未进行改造,后期可进行改造,NA 表示死亡区,不作为判断是否改造完的宜居,无法穿过;
初始化下,该区域可能存在多个宜居区,并目每个宜居区能同时在每个大阳日单位向上下左右四个方向的相邻格子进行扩散,自动将 4 个方向相邻的真空区改造成宜居区;
请计算这个待改造区域的网格中,可改造区是否能全部成宜居区,如果可以,则返回改造的大阳日天教,不可以则返回 −1
输入 row * column 个网格数据,每个网格值枚举值如下: YES,NO,NA ;
样例:
YES YES NO
NO NO NO
NA NO YES
可改造区是否能全部变成宜居区,如果可以,则返回改造的太阳日天数,不可以则返回 −1 。
grid[i][j]只有 3 种情况,YES、NO、NA
输入
YES YES NO
NO NO NO
YES NO NO
输出
2
说明
经过 2 个太阳日,完成宜居改造
输入
YES NO NO NO
NO NO NO NO
NO NO NO NO
NO NO NO NO
输出
6
说明
经过 6 个太阳日,可完成改造
输入
NO NA
输出
-1
说明
无改造初始条件,无法进行改造
输入
YES NO NO YES
NO NO YES NO
NO YES NA NA
YES NO NA NO
输出
-1
说明
右下角的区域,被周边三个死亡区挡住,无法实现改造