ビルをつなぐ通路の本数と最短距離を求めるプログラム。

Problem A
Building Bridges
---- The 2003 ACM Programming Contest World Finals ----

The City Council of New Altonville plans to build a system of bridges connecting all of its downtown buildings together so people can walk from one building to another without going outside. You must write a program to help determine an optimal bridge configuration.
 「New Altonville町の議会が町の各ビルをブリッジでつなぐ計画を立てている。外で歩かなくてもビル間の行き来ができるのがその理由。とにかく最適なプランを決めて欲しい。」

New Altonville is laid out as a grid of squares. Each building occupies a connected set of one or more squares. Two occupied squares whose corners touch are considered to be a single building and do not need a bridge. Bridges may be built only on the grid lines that form the edges of the squares. Each bridge must be built in a straight line and must connect exactly two buildings.
 「New Altonville町はグリッドごとの正方形ブロックに建てられている。各ビルは1つあるいは複数のブロックを使っている。ブロックの角がくっ付いているビルは一つと見なし、間にブリッジは必要ない。ブリッジはグリッド線に沿って建てるべきだ。ブリッジは直線でないといけないし、直接2つのビルをつなぐものでないといけない。」

For a given set of buildings, you must find the minimum number of bridges needed to connect all the buildings. If this is impossible, find a solution that minimizes the number of disconnected groups of buildings. Among possible solutions with the same number of bridges, choose the one that minimizes the sum of the lengths of the bridges, measured in multiples of the grid size. Two bridges may cross, but in this case they are considered to be on separate levels and do not provide a connection from one bridge to the other.
 「ビルの配置が判れば、すべてのビルをつなぐブリッジの最小数を計算してほしい。不可能であれば、つないでいないビルの数を最小にしてほしい。ブリッジの数が同数の解答が複数ある場合には、ブリッジの長さを最短のものにすること。ブリッジが交差するかもしれないが、その場合、ブリッジの高さが互いに違うと考えていい。つまり、ブリッジ同士をつなぐ必要はない。」

The figure below illustrates four possible city configurations. City 1 consists of five buildings that can be connected by four bridges with a total length of 4. In City 2, no bridges are possible, since no buildings share a common grid line. In City 3, no bridges are needed because there is only one building. In City 4, the best solution uses a single bridge of length 1 to connect two buildings, leaving two disconnected groups (one containing two buildings and one containing a single building).
 「町の配置図が4つ示されている。町1に5つのビルがあり、総長4のブリッジ4本でつなぐことができる。町2ではブリッジを建てることは不可能。グリッド線を共有しているビルがないから。町3ではブリッジは必要ない。ビルが1つしかないから。町4では、長さ1のブリッジ1本で2つのビルをつなぐのが最もよい。2つのつながっていないビル群をそのままにする。片方のビル群に2つのビルがつながっているが、もう片方に独立したビルが1つある。

Input
The input data set describes several rectangular cities. Each city description begins with a line containing two integers r and c, representing the size of the city on the north-south and east-west axes measured in grid lengths (1<=r<=50 and 1<=c<=50). These numbers are followed by exactly r lines, each consisting of c hash ("#") and dot (".") characters. Each character corresponds to one square of the grid. A hash character corresponds to a square that is occupied by a building, and a dot character corresponds to a square that is not occupied by a building.
 「入力データに複数の長方形町を示している。各町は二つの整数 r(町の南北方向の長さ、1<=r<=50)、c(東西方向の長さ、1<=c<=50)からスタートし、 その後にr行が続き、それらの行にc個の"#"と"."文字が入る。各文字が正方形ブロックを表し、"#"はビル、"."は空き地を示す。」

The input data for the last city will be followed by a line containing two zeros.
 「入力の最後に0が2つ入る。」

Output
For each city description, print two or three lines of output as shown below. The first line consists of the city number. If the city has fewer than two buildings, the second line is the sentence “No bridges are needed.” If the city has two or more buildings but none of them can be connected by bridges, the second line is the sentence “No bridges are possible.” Otherwise, the second line is “N bridges of total length L” where N is the number of bridges and L is the sum of the lengths of the bridges of the best solution. (If N is 1, use the word “bridge” rather than “bridges.”) If the solution leaves two or more disconnected groups of buildings, print a third line containing the number of disconnected groups.
 「各町に対し、2行あるいは3行を表示すること。1行目に町の番号(City Number)を入れること。町にビルが1つしかない場合、2行目に "No bridges are needed." と表示すること。 町にビルが2つ以上あるけれど、ブリッジでつなぐことができなければ、2行目に “No bridges are possible.” と表示すること。それら以外の場合、2行目に “N bridges of total length L” と表示すること。Nはブリッジの数。N=1の場合、"bridges" の代わりに "bridge" を使うこと。Lはブリッジの最短総長。2つ以上のつないでいないビル群があれば、3行目にその数を表示すること。」

Print a blank line between cases. Use the output format shown in the example.
 「各町に対応する出力データの間に、空白行を入れること。例に示されているフォーマットを利用するといいだろう。」

Sample Input
3 5
#...#
..#..
#...#
3 5
##...
.....
....#
3 5
#.###
#.#.#
###.#
3 5
#.#..
.....
....#
0 0

Output for the Sample Input
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

Comments are closed.

Post Navigation