P5615. 隔断染病计时

场次：2026年10月10日-非AI方向 · 来源：CodeFun2000 P5615

题目描述

身为健康防护软件的编写者，要做的是把长方形屋子里病菌逐步蔓延的经过仿真出来。屋子被画成一张二维格子表，表中的格子只有下面三类：

$0$ 表示尚未染病的人

$1$ 表示已经染病的人

$x$ 表示挡住去路的物体（例如隔板、墙体）

每一轮病菌只会迈进紧贴着的上、下、左、右格子，一轮过去记作 $1$ 小时。请给出把所有还有机会染上的人全部染完所要的最少小时数。只要仍有人因为挡路物体被隔开、再也染不上，就输出 $-1$ 。

首行是两个整数 $r$ 和 $c$ ，依次为格子表的行数与列数，二者之间用一个空格分开。 $1 \le r \le 100$ ， $1 \le c \le 100$ 。

随后恰好 $r$ 行。每行是一串长度为 $c$ 的字符，字符紧挨着书写、中间不留空格，从左到右给出该行每个格子：尚未染病写 $0$ ，已经染病写 $1$ ，挡路物体写 $x$ 。

输出一个整数，表示把还有机会染上的人全部染完所要的最少小时数。若仍有人被挡路物体隔开、始终染不上，则输出 $-1$ 。

输入：

输出：

说明：

为便于对照，下面把同一张表用空格拆开。正式输入里这些空格并不存在。

0 1 0 0
0 0 x 0
x 0 1 0

开局已经染病的，是第 $1$ 行第 $2$ 格，以及第 $3$ 行第 $3$ 格。

尚未染病的人已经没有，答案是 $2$ 。

输入：

3 3
0x0
x1x
00x

输出：

-1

说明：

0 x 0
x 1 x
0 0 x

染病者只有正中间那一个。第 $1$ 小时只能染到正下方那个人；第 $2$ 小时再染到左下角。左上角的右边和下边都是挡路物体，右上角的左边和下边同样被挡住，病菌到不了这两处。因此输出 $-1$ 。