搭桥

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

 */


转载请注明: Five-great的博客 搭桥

上一篇
friend-斐波那契 friend-斐波那契
friend-斐波那契html {overflow-x: initial !important;}:root { –bg-color:#ffffff; –text-color:#333333; –select-text-bg-color:#
2018-10-04
下一篇
ACM ACM
#你好这是我第一篇文章:)题目描述 Description 汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题。在A,B,C三根柱子上, 有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示), 你的目标是在最
2018-09-28