搭桥
题目：搭桥 题目链接：http://codevs.cn/problem/1002/ 题目描述 Description 有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。
输入描述 Input Description 在输入的数据中的第一行包含描述城市的两个整数r 和c, 分别代表从北到南、从东到西的城市大小(1 <= r <= 50 and 1 <= c <= 50). 接下来的r 行, 每一行由c 个(“#”)和(“.”)组成的字符. 每一个字符表示一个单元格。“#”表示建筑物，“.”表示空地。
输出描述 Output Description 在输出的数据中有两行，第一行表示建筑物的数目。第二行输出桥的数目和所有桥的总长度。 样例输入 Sample Input 样例1 3 5 #…# …#… #…#
样例2 3 5 ##… … …#
样例3 3 5 #.### #.#.# ###.#
样例4: 3 5 #.#… … …#
样例输出 Sample Output 样例1 5 4 4
样例2 2 0 0
样例3 1 0 0
样例4 3 1 1 题解
题意概括： 一，先找到该城市有多少楼，即矩阵（城市）中有多少联通块（楼）。 二，通过桥将该城市的楼互通，即每两两楼之间可间接或直接到达。
解题思路： 针对 一， 遍历输入矩阵，遇到不是空地（即是楼的部分），则进入该楼区域，用DFS搜联通块（该楼的全部区域）并过程中给每个楼编号。 针对 二，遍历输入矩阵，遇到满足可以架桥的楼的部分，开始横向或纵向架桥， 遇到其它楼（不是空地且不是同一栋楼），则保存该可行桥信息并结束此次架桥。 找到所有可行桥。按桥长从小到大给所有可行桥排序。然后按从小到大，用并查集来获取最少桥数与最短桥总长。
寻可行桥图解一， 图1中 红线边代表可以作为架桥的桥头，绿线代表作为架桥的桥尾。 2 与 3 满足架桥桥头条件，遍历到2和3处 可以进行架可行桥。
图1二，以 2为例 若横向架长为1的桥 则桥尾可落在 A,B,C 框中，而A,B,C均为空地则增加桥长，直到找到一个可以作为桥尾的边 如图3 找到了C区域，记录桥信息并结束本次架桥，开始纵向架桥，完成后，遍历到 3的位子继续架桥，知道遍历完所有
图2 图3
#include <stdio.h>
#include <string.h>
#define N 55
#define Min(a,b) a>b?b:a
struct node{int q1,q2,qw;}Q[N*N];//存储桥的信息 桥头 桥尾 桥长
int n,c;
int Map[N][N];//输入矩阵
int dx[8]={0,0,-1,1,1,1,-1,-1};//8个方位
int dy[8]={-1,1,0,0,-1,1,-1,1};
int q_ans=0;//所有可行桥数
int F[N*N];//用于并查集头数组
int Q_C=0;//桥总长
int ans=0;//桥总长
//并查集寻头节点（递归版）
int find1(int a){if(F[a]!=a)return a;else return F[a]=find1(F[a]);}
//深搜获得楼房数 以及给楼房编号
void DFS(int x,int y,int num)
{ int xx,yy,k;Map[x][y]=num;//给楼编号
for(k=0;k<8;k++)
{ xx=x+dx[k];yy=y+dy[k];
if(Map[xx][yy]==-1)DFS(xx,yy,num);
}
}
//检查函数 判断两点是否可建桥
int check(int x,int y,int x1,int y1,int flag)
{ //无建筑 或为同一建筑直接返回
if(!Map[x1][y1]||Map[x][y]==Map[x1][y1])return 0;
q_ans++;//可行桥数+1
if(flag==1)Q[q_ans].q1=Map[x][y],Q[q_ans].q2=Map[x1][y1],Q[q_ans].qw=y1-y-1;//当建桥方向为横向（向右）存储桥信息
else Q[q_ans].q1=Map[x][y],Q[q_ans].q2=Map[x1][y1],Q[q_ans].qw=x1-x-1;//当建桥方向为纵向（向下）存储桥信息
return 1;
}
//找桥尾楼
void FQ_end(int x,int y,int flag)
{ int k;
if(flag==1){//横向（向右）方向
for (k=y+1;k<=c;k++)
if(check(x,y,x,k,1)||check(x,y,x+1,k,1)||check(x,y,x-1,k,1))break;
}
else{//纵向（向下）方向
for (k=x+1;k<=n;k++)
if(check(x,y,k,y,2)||check(x,y,k,y+1,2)||check(x,y,k,y-1,2))break;
}
}
//建立可行桥
void BulidQ()
{ int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=c;j++)
{
if(Map[i][j+1]==0&&Map[i][j]!=0){ FQ_end(i,j, 1);} //满足横向（右方）向架桥
if(Map[i+1][j]==0&&Map[i][j]!=0){ FQ_end(i,j, 2);} //满足纵向（下方）向架桥
}
}
//并查集 寻最少桥数与最短桥总长
int BCJ(){
int i,top1,top2,count1=0;
for(i=1;i<=ans;i++)F[i]=i;//初始化
for(i=1;i<=q_ans;i++)//从小到达遍历可行桥
{
top1=find1(Q[i].q1);//找到该桥头楼的主楼（头节点）
top2=find1(Q[i].q2);//找到该桥尾楼的主楼（头节点）
if(top1!=top2){//若两主楼不是同一楼，则通过该桥建立连接共用主楼
F[top1]=top2;
count1++;//桥数+1
Q_C+=Q[i].qw;//更新桥总长 桥总长+该桥长度
}
}
return count1;
}
int main()
{ int i,j;char z;int num=1;
memset(Map,0,sizeof(Map));
memset(F,0,sizeof(F));
scanf("%d%d",&n,&c);
for (i=1;i<=n;i++)
for (j=1;j<=c;j++)
while(1)//处理字符串
{
scanf("%c",&z);
if(z=='#'){Map[i][j]=-1;break;}
if(z=='.'){Map[i][j]=0;break;}
}
//获得楼房数 以及给楼房编号
for (i=1;i<=n;i++)
for (j=1;j<=c;j++)
if(Map[i][j]==-1)DFS(i,j,num),ans++,num++;
BulidQ();
//给桥长排序从小到大（选择排序）
for(i=1;i<q_ans;i++)
for(j=i+1;j<=q_ans;j++)
if(Q[i].qw>Q[j].qw){node tem=Q[i];Q[i]=Q[j]; Q[j]=tem;}
int res=BCJ();
printf("%d\n%d %d\n",ans,res,Q_C);
return 0;
}
/*
5 5
##...
...##
###..
..###
...##
3 5
#...#
..#..
#...#
5 5
##...
....#
#...#
##...
..###
*/腾讯云开发者
