1758: STEMA-P-5 黏菌繁殖

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

一个 n 行 m 列的网格,其中的一个格子有一种黄色黏菌,其余格子为适宜黏菌生长的麦片格子和不适宜黏菌生长的灰色格子。

如果相邻格子(上、下、左、右)适宜生长,黏菌会在一天之内将相邻的麦片格子布满黏菌。 

给定 n 行 m 列的网格,请计算黏菌会在多少天之内布满所有适宜生长的麦片格子;

如果黏菌无法布满所有适宜生长的麦片格子,则输出 -1。 

例如:n = 4,m = 4;4 行 4 列的网格如下(黄色格子为黏菌格子): 

黏菌会在 4 天之内布满所有适宜生长的麦片格子,黏菌生长情况如下:

输入

第一行输入两个整数 n、m(3≤n≤100,3≤m≤100),表示网格的行数和列数,整数之间以一个空格隔开; 

接下来输入 n 行,每行 m 个整数,整数只能为 0、1、2 中的一个;

0 表示灰色格子,1 表示麦片格子,2 表示黏菌格子,整数之间以一个空格隔开。 

数据保证有 1 个以上的麦片格子,且仅有 1 个黏菌格子。

输出

输出一个整数,表示黏菌会在多少天之内布满所有适宜生长的麦片格子;如果黏菌无法布满所有适宜生长的麦片格子,则输出 -1。

样例输入 复制

4 4
0 0 1 0
1 1 2 1
1 0 1 1
1 1 1 0

样例输出 复制

4

提示

宽度优先搜索 国考真题(2025年6月)

来源/分类