题目描述
小华是一位痴迷于模拟生命现象的计算机科学爱好者，尤其钟情于探索经典的“生命游戏”。此刻，他正沉浸在实验室的荧光屏前，研究一款简化版的细胞自动机模型。屏幕上是一个由无数方格构成的虚拟世界，每个方格代表一个细胞单元。游戏开始时，小华可以自由选择在哪些方格中“播种”初始生命（标记为存在生命）。随后，世界将按照一个简单而神奇的规则演化：在每一秒的开始，如果一个原本没有生命的格子，其上、下、左、右四个相邻格子中至少有一个存在生命，那么这个格子就会在下一秒诞生新的生命。而已经存在的生命则永不消逝。
小华被一个有趣的挑战所吸引：他希望在未来的某个瞬间，屏幕上恰好呈现出他精心设计的目标图案——一个由特定方格拥有生命构成的图形。他明白，不同的初始“播种”方式，会导致达到目标图案所需的时间不同。他渴望探索的是：如果允许他在初始时任意放置生命（甚至可以不放置任何生命），那么从游戏开始算起，最多需要经过多少秒，才能确保在某一秒结束时，屏幕上的生命分布正好与他想要的目标图案完全一致？
简单来说，给定一个n 行m 列的网格，代表小华的虚拟世界。网格的边框（即最外层一圈格子）保证都是没有生命的。你需要根据小华提供的目标图案，计算出他最多需要等待多少秒，才能在游戏演化的某一秒结束时，恰好让网格上的生命分布与目标图案完全匹配。
输入
第一行包含两个整数n 和m(1 ≤ n, m ≤ 1000)，表示网格的行数和列数。
接下来n 行，每行包含一个长度为m 的字符串，描述小华的目标图案：
# 表示要求这个格子有生命。
. 表示要求这个格子没有生命。
保证网格的边框（第一行、最后一行、第一列、最后一列的所有格子）都是'.'(即没有生命)。
输出
输出一行一个整数，表示小华最多需要等待的秒数。即在初始可以任意放置生命的前提下，要保证在某一秒结束时恰好出现目标图案，所需的最大时间。
样例输入输出
输入#1
复制
10 9
.........
...#.....
..###....
.#####...
..####...
...####..
...#####.
....###..
.....#...
.........
提示
初始时在(4,4)和(7,6)两个位置放置生命，生命蔓延的过程如下图所示，可以看到最多2s 可以达到目标图案。
【数据范围约定】
对于30%的数据，1≤n,m≤100
对于65%的数据，1≤n,m≤400
对于100%的数据，1≤n,m≤1000