# LA 2721

Jump to navigation
Jump to search

## LA 2721 - Building Bridges[edit]

## Summary[edit]

Given is a set of buildings, each building is a connected set of unit squares in a grid. You may connect the buildings by building straight bridges along the grid lines. Find such a set of bridges that:

- The number of disjoint building groups is minimal.
- Among all such solutions, the total length of the bridges is minimal.

## Explanation[edit]

This is a special case of a minimum spanning tree problem in a graph where buildings are vertices and edges are possible bridges.

First, run a BFS to find and label the buildings. Then, the best way to construct the set of edges is to traverse the grid lines one after another.

## Input[edit]

3 5 #...# ..#.. #...# 3 5 ##... ..... ....# 3 5 #.### #.#.# ###.# 3 5 #.#.. ..... ....# 0 0

## Output[edit]

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