題目 1941:
藍(lán)橋杯算法提高VIP-Building Bridges
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 1 解決: 0
題目描述
新奧德衛(wèi)萊城市委員會計(jì)劃建造一個(gè)連接系統(tǒng)來連接所有市中心的建筑，這樣人們從一個(gè)建筑去另一個(gè)建筑時(shí)就不用走到外面了。你要寫一個(gè)程序來幫忙確定建造方案。
新奧德衛(wèi)萊市是正方形網(wǎng)狀布局，每個(gè)建筑物占著一些連通的格子，兩個(gè)有建筑物的格子如果有角接觸就算相連，不需要連接道路。道路只能在正方形的邊上建造，并且只能是直線且連接兩個(gè)建筑。
給你一個(gè)建筑示意圖，你要算出連接所有建筑的最小道路數(shù)。如果這是不可能的，找出最少的無法連接的建筑群數(shù)。在可連接所有建筑物的情況下，如果多種方案道路數(shù)都是最小的，選擇在網(wǎng)格中道路總長度最小的方案。道路可以互相穿過，但在這種情況下道路被判定互不相干，之間無法連接。
下圖說明了4種可能的城市配置。城市1包含5個(gè)建筑，被4條道路連接起來，總長度為4。城市2中，因沒有建筑共享網(wǎng)格線所以無法建立道路。在城市3中，因?yàn)橹挥?個(gè)建筑所以我們不需要道路。在城市4中，最好方案是用1條長度為1的道路連接兩個(gè)城市，剩下兩個(gè)不連通的建筑群（一個(gè)是兩個(gè)建筑，一個(gè)是一個(gè)建筑）。
左上是城市1 ，中上是建路后的城市1 ，右上是不能建路的城市2，左下是不需要建路的城市3，中下是城市4，右下是建路后的城市4。
新奧德衛(wèi)萊市是正方形網(wǎng)狀布局，每個(gè)建筑物占著一些連通的格子，兩個(gè)有建筑物的格子如果有角接觸就算相連，不需要連接道路。道路只能在正方形的邊上建造，并且只能是直線且連接兩個(gè)建筑。
給你一個(gè)建筑示意圖，你要算出連接所有建筑的最小道路數(shù)。如果這是不可能的，找出最少的無法連接的建筑群數(shù)。在可連接所有建筑物的情況下，如果多種方案道路數(shù)都是最小的，選擇在網(wǎng)格中道路總長度最小的方案。道路可以互相穿過，但在這種情況下道路被判定互不相干，之間無法連接。
下圖說明了4種可能的城市配置。城市1包含5個(gè)建筑，被4條道路連接起來，總長度為4。城市2中，因沒有建筑共享網(wǎng)格線所以無法建立道路。在城市3中，因?yàn)橹挥?個(gè)建筑所以我們不需要道路。在城市4中，最好方案是用1條長度為1的道路連接兩個(gè)城市，剩下兩個(gè)不連通的建筑群（一個(gè)是兩個(gè)建筑，一個(gè)是一個(gè)建筑）。
左上是城市1 ，中上是建路后的城市1 ，右上是不能建路的城市2，左下是不需要建路的城市3，中下是城市4，右下是建路后的城市4。
輸入格式
輸入包含多座城市，每個(gè)城市的描述第一行有2個(gè)整數(shù)r和c（1<=r,c<=50），表示這個(gè)城市的南北距離和東西距離，之后接著r行，每行有c個(gè)“#”或“.”，每個(gè)字符表示網(wǎng)格中的一個(gè)格子?！?”表示那個(gè)格子中有建筑，“.” 表示那個(gè)格子中沒有建筑。數(shù)據(jù)的最后一個(gè)城市是由兩個(gè)0組成。
輸出格式
對于每個(gè)城市，像樣例那樣輸出兩到三行。第一行是城市編號。如果城市只有少于兩個(gè)建筑，就在第二行輸出“No bridges are needed.”。如果城市有兩個(gè)及以上個(gè)建筑且任意兩個(gè)建筑都不能被連接，就在第二行輸出“No bridges are possible.”。否則，就在第二行輸出“N bridges of total length L”，其中N是道路數(shù)，L是最優(yōu)方案的道路長度。（如果N是1，就用bridge代替bridges）。如果最終方案剩下了多個(gè)建筑群，在第三行輸出建筑群數(shù)。
每組數(shù)據(jù)間用空行隔開。見下面樣例。
每組數(shù)據(jù)間用空行隔開。見下面樣例。
樣例輸入
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
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情