LA 2721

From Algorithmist
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