3702: 【BFS】2024E-火星改造

金币值:1 时间限制:2.000 s 内存限制:128 M
正确:133 提交:238 正确率:55.88% 命题人:

题目描述

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。

输入样例    复制

YES YES NO
NO NO NO
YES NO NO

输出样例    复制

2