See All ACM 2003 Final Problems (problems.pdf)
The Problem: Building Bridges.
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 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. 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).
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.
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.
Print a blank line between cases. Use the output format shown in the example.
Sample Input Sample Output 3 5 City 1 #...# 4 bridges of total length 4 ..#.. #...# 3 5 City 2 ##... No bridges are possible. ..... 2 disconnected groups ....# 3 5 City 3 #.### No bridges are needed. #.#.# ###.# 3 5 City 4 #.#.. 1 bridge of total length 1 ..... 2 disconnected groups ....#
Minimal Spanning Tree Algorithm -- MST is essential part of undergraduate course of algorithm and data structure.
The following program will convert the given problem into a MST problem. The basic idea is like this:
First of all, detect all buildings of a city from the input of the city. This can be done by recursively expanding the building from any "#" cell. Assign unique building number (starting from 1) for each building. With those "." cells, their building number will be 0. After this step, we get a two dimmensional array of integers:
Array2D<int> bno(ct.rows, ct.cols);
where bno(i,j) is the building number for cell (i, j) of grid from the city input. For example, with sample input of "City 1", the two dimensional array bno(3,5) will look like:
1 0 0 0 2
0 0 3 0 0
4 0 0 0 5
With sample input of "City 3", the two dimensional array bno(3,5) will look like:
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
In the case of "City 3", since there is only one building, so no bridges are needed.
Secondly, find out the shortest bridges between any two buildings if any. This goal can be achieved by scanning all horizontal bridges and scanning all vertical bridges. A horizontal bridge is a path on one horizontal grid line, each edge on the path is not on any building. A vertical bridge is a path on one vertical grid line, each edge on the path is not on any building. Without losing generality, we can ignore the last grid line on both directions. After scanning all bridges, we can build a two dimensional array like this:
Array2D<int> dist(TotalBuildings, TotalBuildings);
where dist(i,j) is the length of shortest bridge between building i and building j. If there is no bridge between them, dist(i,j) will be 0.
For sample input of "City 1", the array (5x5) will be like:
0 3 1 1 0
3 0 1 0 1
1 1 0 1 1
1 0 1 0 3
0 1 1 3 0
Finally, based on the data from the second step, we can view all buildings as vertice, bridges as edges of a graph. With this graph, we can find out its minimal spanning forest, which contains disconnected minimal spanning trees. Then we can report the number of disconnected spanning trees, the total length of the bridges etc. For sample input of "City 1", the bridges we find out would be:
(1,3),(1,4),(2,3),(2,5).
That is, the bridges from building 1 to 3, building 1 to 4, building 2 to 3, building 2 to 5. All bridges are of length 1. These bridges connect all buildings in "City 1".
//Author: Victor Zeng 12/20/2006
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <memory>
using namespace std;
namespace acm_bridges_problem_2003A {
//dynamic two dimensional array
template <class T> class Array2D {
int _row, _col;
vector<T> _stor;
public:
Array2D(int r, int c):_row(r),_col(c),_stor(r*c)
{
}
~Array2D()
{
}
T &operator()(int i, int j)
{ return _stor[i*_col+j];
}
const T &operator()(int i, int j) const
{ return _stor[i*_col+j];
}
int rows() const {return _row;}
int cols() const {return _col;}
};
struct city {
Array2D<char> grids;
int rows;
int cols;
city(int r, int c):rows(r),cols(c),grids(Array2D<char>(r,c)) {}
};
vector<city> cities;
//the function read_bridges_in will read the input data into the array
void read_cities_in()
{
int rows, cols;
char c;
do {
cin>>rows;
cin>>cols;
if (rows==0||cols==0)
break; //finish input
city ct(rows,cols);
for (int i=0; i<ct.rows; i++)
for (int j=0; j<ct.cols; j++)
{
cin>>c;
ct.grids(i,j) = c;
}
cities.push_back(ct);
} while(1);
}
//Find out possible bridges with minimal length to connect the buildings
//input int v -- number of vertices in the graph
//input int *dist -- array of size v*v or two dimensional array dist[v][v]
// dist[i][j] == 0 if there is no edge between i, j
// dist[i][j] >0 if length of the edge between i, j
void mst(Array2D<int> &dist, int v)
{
list<pair<int,int>> edges;
list<pair<int,int>>::iterator iter, e;
int i, j, k;
//sort bridges according to length
for (i=0; i<v; i++)
for(j=i; j<v; j++)
{ if(dist(i,j)>0)
{
iter = edges.begin();
e = edges.end();
while (iter!=e)
{
if (dist(i,j)<=dist(iter->first, iter->second))
break;
iter++;
}
edges.insert(iter,make_pair(i,j));
}
}
//Assign a group # to each vertice.
//If two vertice have same group number, indicate that they can be linked
vector<int> gn(v);
int nextg=1, totalg=v, totallen=0, totalb=0;
iter = edges.begin();
e = edges.end();
while (iter!=e)
{
if (gn[iter->first]!=gn[iter->second]||!gn[iter->first]&&!gn[iter->second])
{
totalb++; //number of bridges, i.e. edges
totallen += dist(iter->first, iter->second);
totalg--;
if(!gn[iter->first]&&!gn[iter->second])
{
gn[iter->first] = nextg;
gn[iter->second] = nextg;
nextg++;
}
else if(!gn[iter->first])
{
gn[iter->first] = gn[iter->second];
}
else if(!gn[iter->second])
{
gn[iter->second] = gn[iter->first];
}
else //merge two islands
{
for (k=0; k<v; k++)
if (gn[k]==gn[iter->second])
gn[k] = gn[iter->first];
}
}
iter++;
}
if (totallen==0)
{
cout<<"No bridges are possible."<<endl;
cout<<totalg<<" disconnected group";
if(totalg>1) cout<<"s";
cout<<endl;
}
else
{
cout<<totalb<<" bridge";
if (totalb>1) cout<<"s";
cout<<" of total length "<<totallen<<endl;
if (totalg>1)
cout<<totalg<<" disconnected groups"<<endl;
}
}
//expand a building from one '#'
void expand(const city &ct, Array2D<int> &bno, int bn, int x, int y)
{
bno(x,y) = bn;
if (x>0)
{
if (y>0 && bno(x-1,y-1)==0 && ct.grids(x-1, y-1)=='#')
expand(ct, bno, bn, x-1, y-1);
if (ct.grids(x-1, y)=='#' && bno(x-1,y)==0 )
expand(ct, bno, bn, x-1, y);
if ( y<(ct.cols-1)&& bno(x-1,y+1)==0 && ct.grids(x-1, y+1)=='#')
expand(ct, bno, bn, x-1, y+1);
}
if (y>0 && bno(x,y-1)==0 &&ct.grids(x,y-1)=='#')
expand(ct, bno, bn, x, y-1);
if (y<(ct.cols-1)&& bno(x,y+1)==0 && ct.grids(x, y+1)=='#')
expand(ct, bno, bn, x, y+1);
if (x<(ct.rows-1))
{
if (y>0 && bno(x+1,y-1)==0 &&ct.grids(x+1,y-1)=='#')
expand(ct, bno, bn, x+1, y-1);
if ( ct.grids(x+1, y)=='#' && bno(x+1,y)==0 )
expand(ct, bno, bn, x+1, y);
if ( y<(ct.cols-1)&& bno(x+1,y+1)==0 && ct.grids(x+1, y+1)=='#')
expand(ct, bno, bn, x+1, y+1);
}
}
//scan for vertical bridges
void scanbridgesbycols(const city &ct, Array2D<int> &bno, Array2D<int> &dist)
{ int i, j, k;
for (j=0; j<ct.cols; j++)
{
i = 0;
//skip "white space" in the beginning of the vertical line
while ( i<ct.rows && (j==0||ct.grids(i,j-1)=='.')&& ct.grids(i,j)=='.')
i++;
while(i<ct.rows)
{
//skip building edges
while(i<ct.rows && (j==0&&ct.grids(i,j)=='#'||j>0&&(ct.grids(i,j-1)=='#'||ct.grids(i,j)=='#')))
i++;
//bridge start at i if i<ct.rows
k = i;
while(i<ct.rows&&(j==0||ct.grids(i,j-1)=='.')&&ct.grids(i,j)=='.')
i++;
//----------------------------
//2. Update shortest bridge length
if (k>0&&i<ct.rows)
{ //[k,j]---[i,j] is a bridge to link [i or i-1,k-1] [i or i-1, j]
int b1 = (j>0?max(bno(k-1,j-1), bno(k-1,j)):bno(k-1,j)); //building one
int b2 = (j>0?max(bno(i,j-1), bno(i,j)):bno(i,j)); //building two
if ( dist(b1-1, b2-1)==0||dist(b1-1, b2-1)>(i-k))
dist(b1-1, b2-1) = i-k;
if ( dist(b2-1, b1-1)==0||dist(b2-1, b1-1)>(i-k))
dist(b2-1, b1-1) = i-k;
}
}
}
}
//scan for horizontal bridges
void scanbridgesbyrows(const city &ct, Array2D<int> &bno, Array2D<int> &dist)
{ int i, j, k;
for (i=0; i<ct.rows; i++)
{
j=0;
//skip "white space" in the beginning of the horizontal line
while ( j<ct.cols && ct.grids(i,j)=='.' && (i==0||ct.grids(i-1,j)=='.'))
j++;
while(j<ct.cols)
{
//skip buildingedges
while(j<ct.cols && (i==0&&ct.grids(i,j)=='#'||i>0&&(ct.grids(i-1,j)=='#'||ct.grids(i,j)=='#') ))
j++;
//----------------------------
//1. find a bridge
k = j;
while (j<ct.cols&&(i==0||ct.grids(i-1,j)=='.')&&ct.grids(i,j)=='.')
j++;
//----------------------------
//2. Update shortest bridge length
if (k>0&&j<ct.cols)
{ //[i,k]---[i,j-1] is a bridge to link [i or i-1,k-1] [i or i-1, j]
int b1 = (i>0?max(bno(i-1,k-1), bno(i,k-1)):bno(i,k-1)); //building one
int b2 = (i>0?max(bno(i-1,j), bno(i,j)):bno(i,j)); //building two
if ( dist(b1-1, b2-1)==0||dist(b1-1, b2-1)>(j-k))
dist(b1-1, b2-1) = j-k;
if ( dist(b2-1, b1-1)==0||dist(b2-1, b1-1)>(j-k))
dist(b2-1, b1-1) = j-k;
}
}
}
}
//process a city, given city no from 1 to cities.size()
void processcity(int cno)
{
cout<<"City "<<cno<<endl;
const city &ct = cities[cno-1];
Array2D<int> bno(ct.rows, ct.cols);
int nextbuildingno=0;
for (int x=0; x<ct.rows; x++)
for (int y=0; y<ct.cols; y++)
if (bno(x,y)==0 && ct.grids(x,y)=='#')
{ //create a building from here
expand(ct, bno, ++nextbuildingno, x, y);
}
if (nextbuildingno<=1) //find no more than one group
{
cout<<"No bridges are needed."<<endl;
return;
}
//use dist to store minimal bridge length between any two buildings,
//0 means no bridge possible
Array2D<int> dist(nextbuildingno, nextbuildingno);
//scan horizontal bridges
scanbridgesbyrows(ct, bno, dist);
//scan vertical bridges
scanbridgesbycols(ct, bno, dist);
//do minimal spanning tree procedure to find connecting bridges with minimal length
mst(dist, nextbuildingno);
}
void BuildBridges()
{
read_cities_in();
for (int i=0; i<cities.size(); i++)
{
processcity(i+1);
cout<<endl;
}
}
}