G-lxy的通风报信_河南萌新联赛2024第（二）场：南阳理工学院

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在 $n$ × $m$ 的平面星球里（ $5 <= n$ ， $m <= 1000$ ），存在着 $a$ 支军队 ( $2 <= a <= 50$ ) , 和 $b$ 支驻扎在地图中的敌军 ( $0 <= b <= n * m - a$ ) ，你需要确保所有军队全部合并 .

军队坐标假设为 ( $x_i$ , $y_i$ ) ，行军一天可以到达( $x_{i + 1}$ , $y_i$ )或者 ( $x_{i - 1}$ , $y_i$ ) 或者( $x_i$ , $y_{i + 1}$ ) 或者 ( $x_i$ , $y_{i - 1}$ )，在与另外一支军队相遇时自动合并到另一支军队，你的部队需要避免与敌军起冲突。

战事紧急，身为司令，你需要快速计算出最少多少天所有军队全部合并完毕，如果必须跟敌军发生冲突请输出 No ,否则输出最少的天数。

注意：

在一支军队移动时，其他军队不可移动。

军队合并是依次进行的，且起点和终点都必须是军队，起点终点不固定，每次行军，可以任意指定两个现存在地图中的不同军队作为起点终点。例如有三个军队A，B，C，A->B，A合并B，B再合并C。也可以A->B,C->B。

输入描述:

输入 ,（， ）
输入行，每行列，
每列用 表示军队
# 表示敌军
 表示可移动区域。

输出描述:

如果军队之间可以全部合并，输出需要多少步
反之输出No

示例1

输入

复制

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

输出

复制

说明

示例2

输入

复制

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

输出

复制

示例3

输入

复制

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

输出

复制

No