题目 1941:
蓝桥杯算法提高VIP-Building Bridges
时间限制: 3s
内存限制: 192MB 提交: 1 解决: 0
题目描述
新奥德卫莱城市委员会计划建造一个连接系统来连接所有市中心的建筑，这样人们从一个建筑去另一个建筑时就不用走到外面了。你要写一个程序来帮忙确定建造方案。
新奥德卫莱市是正方形网状布局，每个建筑物占着一些连通的格子，两个有建筑物的格子如果有角接触就算相连，不需要连接道路。道路只能在正方形的边上建造，并且只能是直线且连接两个建筑。
给你一个建筑示意图，你要算出连接所有建筑的最小道路数。如果这是不可能的，找出最少的无法连接的建筑群数。在可连接所有建筑物的情况下，如果多种方案道路数都是最小的，选择在网格中道路总长度最小的方案。道路可以互相穿过，但在这种情况下道路被判定互不相干，之间无法连接。
下图说明了4种可能的城市配置。城市1包含5个建筑，被4条道路连接起来，总长度为4。城市2中，因没有建筑共享网格线所以无法建立道路。在城市3中，因为只有1个建筑所以我们不需要道路。在城市4中，最好方案是用1条长度为1的道路连接两个城市，剩下两个不连通的建筑群（一个是两个建筑，一个是一个建筑）。
左上是城市1 ，中上是建路后的城市1 ，右上是不能建路的城市2，左下是不需要建路的城市3，中下是城市4，右下是建路后的城市4。
新奥德卫莱市是正方形网状布局，每个建筑物占着一些连通的格子，两个有建筑物的格子如果有角接触就算相连，不需要连接道路。道路只能在正方形的边上建造，并且只能是直线且连接两个建筑。
给你一个建筑示意图，你要算出连接所有建筑的最小道路数。如果这是不可能的，找出最少的无法连接的建筑群数。在可连接所有建筑物的情况下，如果多种方案道路数都是最小的，选择在网格中道路总长度最小的方案。道路可以互相穿过，但在这种情况下道路被判定互不相干，之间无法连接。
下图说明了4种可能的城市配置。城市1包含5个建筑，被4条道路连接起来，总长度为4。城市2中，因没有建筑共享网格线所以无法建立道路。在城市3中，因为只有1个建筑所以我们不需要道路。在城市4中，最好方案是用1条长度为1的道路连接两个城市，剩下两个不连通的建筑群（一个是两个建筑，一个是一个建筑）。
左上是城市1 ，中上是建路后的城市1 ，右上是不能建路的城市2，左下是不需要建路的城市3，中下是城市4，右下是建路后的城市4。
输入格式
输入包含多座城市，每个城市的描述第一行有2个整数r和c（1<=r,c<=50），表示这个城市的南北距离和东西距离，之后接着r行，每行有c个“#”或“.”，每个字符表示网格中的一个格子。“#”表示那个格子中有建筑，“.” 表示那个格子中没有建筑。数据的最后一个城市是由两个0组成。
输出格式
对于每个城市，像样例那样输出两到三行。第一行是城市编号。如果城市只有少于两个建筑，就在第二行输出“No bridges are needed.”。如果城市有两个及以上个建筑且任意两个建筑都不能被连接，就在第二行输出“No bridges are possible.”。否则，就在第二行输出“N bridges of total length L”，其中N是道路数，L是最优方案的道路长度。（如果N是1，就用bridge代替bridges）。如果最终方案剩下了多个建筑群，在第三行输出建筑群数。
每组数据间用空行隔开。见下面样例。
每组数据间用空行隔开。见下面样例。
样例输入
3 5 #...# ..#.. #...# 3 5 ##... ..... ....# 3 5 #.### #.#.# ###.# 3 5 #.#.. ..... ....# 0 0
样例输出
City 1 4 bridges of total length 4 City 2 No bridges are possible. 2 disconnected groups City 3 No bridges are needed. City 4 1 bridge of total length 1 2 disconnected groups