搭桥

题目：搭桥
题目链接：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
##...
....#
#...#
##...
..###

 */