题目描述

有一个无穷大的网格，一开始每个格子有一个颜色，可能是黑色或者白色。 到 这个子矩形内的格子的颜色是给定的，其他格子均为白色。

你可以进行若干次操作，一次操作中，你需要选定上、下、左和右中的一个方向，然后对于每个黑色的格子，它对应方向的那个格子也会变成黑色的格子。

你需要回答：至少进行几次操作，可以让任意两个黑色格子八联通。

两个黑色格子八联通当且仅当它们有一条公共边或者一个公共顶点或者存在一个黑色格子同时和它们八联通，也就 是说在只向相邻或者对角的格子走且只经过黑色格子的条件下互相可达。

输入格式

第一行两个整数 ，表示网格的大小。 接下来 行，每行一个长为 的 01 字符串，第 个串的第 位为 则表示位于 的格子是黑色，否则是白 色。

输出格式

一行一个整数，最少的操作次数。 输入输出样例 输入 #1 5 4 1100 1000 0011 0000 0001

输出 #1 1

输入 #2 8 10 0000000011 0000000000 0000000000 0000000010 0000000000 0001010100 0000000000 0001000100

输出 #2 3

输入 #3 及 输出 #3 见下发目录中的 fluid3.in 和 fluid3.ans 。

样例解释 对于第一组样例，一开始网格如下图所示。


进行一次操作，选择下方向，网格会变成如下图所示的样子（标红的是新变为黑色的格子），任意两个黑格都八联通。可以证明这是最少的操作次数。


子任务

Subtask 1 (10 分)： 保证 n,m<=3

Subtask 2 (20 分)：保证 n,m<=80

Subtask 3 (20 分)： 保证黑色格子的数量不超过20 .

Subtask 4 (5 分)：保证m=1 .

Subtask 5 (44 分)： 保证n,m.<=300

Subtask 6 (1 分)：没有特殊限制