骑士战胜魔王

题号：NC237065
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

牛牛在玩一款模拟游戏。

地图是一个由 $'.','\#', '*'$ 三种字符组成的大小为 $n*m$ 的方格图，其中 $'.'$ 代表空格（空格可以被占据）、 $'\#'$ 代表城墙（城墙不可被通过）、 $'*'$ 代表一个普通骑士，初始时每个普通骑士都单独占据了地图上自己所在的那一个格子。

每隔一秒，所有骑士都会进行一轮拓展。每轮拓展，骑士将会把和自己已经占据的格子相邻（这里的“相邻”指代两个格子具有共用边，下同）且未被其它骑士占领的格子给占据。若在一轮拓展中，有多个骑士想占据同一个未被占据的格子，那么这个格子将会被这些骑士里初始坐标中横坐标最小的骑士占据，若初始坐标中横坐标最小的骑士有多个则这个格子会被横坐标最小的骑士中纵坐标最小的骑士所占据（这样的骑士只有一个）。

游戏开始时牛牛可以指定若干个普通骑士赋予他们圣光，将他们进阶为圣光骑士，但圣光不能改变骑士们拓展领域的规则。

游戏中有一个大魔王，它会从地图的左上角（既编号为 $(1,1)$ 的格子）向位于右下角（既编号为 $(n, m)$ 的格字）的村庄侵蚀过去（通过相邻且可以到达的格子），魔王的侵蚀速度可以认为是无穷大（瞬间即可到达（如果可以到达的话））的，魔王可以通过普通骑士所占据的格子但是不能通过被圣光骑士所占据的格子。

圣光骑士需要保护村庄（不让魔王到达村庄），牛牛想知道为了阻止魔王侵蚀村庄，至少需要多久的时间给骑士进行防守（占据格子），且在时间最短的前提下至少需要给几个骑士赋予圣光。

输入描述:

输入第一行两个整数  。
接下来输入一个  的字符矩阵，描述整个地图。
保证：

输出描述:

输出共一行两个整数分别代表骑士防守需要的最小时间以及在时间最小化的前提下最少需要给几个骑士赋予圣光。
特别的，如果无法封锁魔王通往村庄的道路则输出 。

示例1

输入

复制

6 7
.......
...#.*.
..##..*
....*..
.*.#.#.
...*...

输出

复制

1 2

说明

一秒钟后通过初始坐标在： 和  的点就可以封锁掉魔王通向村庄的道路。

示例2

输入

复制

3 3
#.#
.#.
#.#

输出

复制

0 0

说明

若魔王的入口或村庄的入口被封锁，或者魔王不存在能够通向村庄的路，则骑士不需要拓展就可以阻止魔王。
图中测试案例中可能不存在骑士。

示例3

输入

复制

3 3
*..
...
..*

输出

复制

0 1

说明

只需要将  或  位置的骑士进阶为圣光骑士就可以阻断魔王的路了。

示例4

输入

复制

5 5
.....
..#..
.#*#.
..#..
.....

输出

复制

-1

说明

不论经过多久骑士都不可能阻断魔王的通路。