题目内容

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

$0$ 表示尚未染病的人

$1$ 表示已经染病的人

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

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

输入描述

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

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

输出描述

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

样例1

输入

3 4
0100
00x0
x010

输出

2

说明

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

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

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

• 第 $1$ 小时：第 $1$ 行第 $2$ 格把左边、右边、下边三个人染上；第 $3$ 行第 $3$ 格把左边和右边两个人染上。它的正上方是挡路物体，过不去。
• 第 $2$ 小时：还剩三个人，分别位于第 $1$ 行最右、第 $2$ 行最左、第 $2$ 行最右，这一小时也被染上。

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

样例2

输入

3 3
0x0
x1x
00x

输出

-1

说明

0 x 0
x 1 x
0 0 x

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