Description

你被请来参加偶像的全国巡回演唱会，并且你的任务是带领大家一起为偶像打call！但是观众中有一小撮反串黑粉，你的目标是带领真爱粉用爱来感♂化黑粉，保证演唱会的成功进行。

演唱会观众区域由一个 n x m 的矩阵表示， 在这个矩阵中：

• “.” 表示空白位置
• “#” 表示障碍物
• “x” 表示黑粉所在的位置

你将派出k名真爱粉来压制黑粉。真爱粉可以位于空白位置或者与黑粉所在的位置重合。所有的真爱粉所在的位置必须形成 一个连通块 。所求的连通块必须覆盖所有的黑粉位置。并且真爱粉的 连通块 只能由水平方向和/或竖直方向上相邻的其它真爱粉连接形成。

求最少需要多少名真爱粉来感化黑粉。如果不能完成，输出-1。

Input

第一行有两个整数n和m。代表矩阵有n行m列。
接下来有一个n行m列的字符矩阵，代表演唱会的观众区域。

保证矩阵中至少有一个“x“字符。

Output

输出一个整数k，代表最少需要多少真爱粉才可以压制黑粉。

如果无解，输出-1。

Sample

Sample 1

Input

3 3
...
x.x
...

Output

3

Explanation

...
OOO
...

最少派出3名真爱粉来覆盖所有黑粉所在的位置。
（“O” 代表真爱粉，下同）

Sample 2

Input

3 3
...
x#x
...

Output

5

Explanation

最少派出5名真爱粉来覆盖所有黑粉所在的位置。

可行解有：

...
O#O
OOO

或者

OOO
O#O
...

Sample 3

Input

3 3
.#.
x#x
.#.

Output

-1

Explanation

无法形成一个连通块来覆盖所有黑粉。

Sample 4

Input

3 4
.#.#
xxx.
.#.x

Output

5

Limitation

1 <= n, m <= 32

• TimeLimit: 1s
• MemLimit: 256MB

Hint

Follow up problem for : https://leetcode-cn.com/problems/cut-off-trees-for-golf-event

Source

无授权禁止转载