首页 > 代码库 > codevs1002 搭桥
codevs1002 搭桥
1002 搭桥
有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。
在输入的数据中的第一行包含描述城市的两个整数r 和c, 分别代表从北到南、从东到西的城市大小(1 <= r <= 50 and 1 <= c <= 50). 接下来的r 行, 每一行由c 个(“#”)和(“.”)组成的字符. 每一个字符表示一个单元格。“#”表示建筑物，“.”表示空地。
在输出的数据中有两行，第一行表示建筑物的数目。第二行输出桥的数目和所有桥的总长度。
样例1
3 5
#...#
..#..
#...#
样例2
3 5
##...
.....
....#
样例3
3 5
#.###
#.#.#
###.#
样例4:
3 5
#.#..
.....
....#
样例1
5
4 4
样例2
2
0 0
样例3
1
0 0
样例4
3
1 1
这个题，跃跃欲试了好久，今天终于AC
为什么看起来复杂？因为图形是放在格子里，这就说明每个建筑物有四个角，怎么办，蒙圈？
不如将其看做一个点，一步一步写
下面是一些类似代码解释的东西
以字符串的形式输入地图的每一行
统计地图中的建筑物数量
把所有点的父亲都初始化为自己（依次编号）
遍历整个地图
遇到不是楼房的点则跳过
找到一个楼房，则以该楼房为中心，再对地图进行一次遍历，同样跳过不是楼房的点
跳过本行以上行的点（已经遍历过），跳过同行且本列以前的点（已经遍历过）
找到目标点（有用的点），并用其在地图上的序号标示
对两个建筑判断能否搭桥
find_bright函数： 排除直接相邻的两点（不用搭桥）
排除斜相邻的点（不用搭桥）
返回-1是不用搭桥，返回0是无法搭桥
在同行或同列可以搭桥，sign是这座桥的长度
犹如加边，把建筑物连起来
最终再统计一遍桥的数目和总长
就是这样
然后再来一点注意事项
1 编号方法如图
2.如图，这是边的由来
3.如图，这是为什么find_bridge函数中用到fabs(x-x1)<=1
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>using namespace std;int buildnum,bridnum,n,m,map[60][60],father[361],lianjie,bridge;int e_num;struct node{ int v,to,from;}e[1000000];char s[60];int find_bridge(int x,int y,int x1,int y1){ if(x==x1&&(fabs(x-x1)==1))return -1; if(y==y1&&(fabs(y-y1)==1))return -1; if((fabs(x-x1)==1)&&(fabs(y-y1)==1))return -1; if(fabs(x-x1)<=1)return fabs(y-y1)-1; if(fabs(y-y1)<=1)return fabs(x-x1)-1; return 0;}int find(int x){ if(father[x]==x)return father[x]; return father[x]=find(father[x]);}int connect(int p1,int p2){ int f1=find(p1); int f2=find(p2); father[f1]=f2;}int cmp(node i,node j){ return i.v<j.v;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",s); for(int j=1;j<=m;j++){ if(s[j-1]==‘.‘)map[i][j]=0; if(s[j-1]==‘#‘)map[i][j]=1,buildnum++; } } for(int i=1;i<=n*m;i++)father[i]=i; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(map[i][j]==0)continue; for(int x=i;x<=n;x++){ for(int y=1;y<=m;y++){ if(x==i&&y<=j)continue; if(map[x][y]==0)continue; int it=find_bridge(i,j,x,y); int one=(i-1)*m+j,two=(x-1)*m+y; if(it==-1){ if(find(one)!=find(two))connect(one,two),lianjie++; continue; } if(it==0)continue; //加边 e[++e_num].from=one; e[e_num].to=two; e[e_num].v=it; } } } } printf("%d\n",buildnum-lianjie); sort(e+1,e+e_num+1,cmp); for(int i=1;i<=e_num;i++){ if(find(e[i].from)!=find(e[i].to)) connect(e[i].from,e[i].to),bridge+=e[i].v,bridnum++; } printf("%d %d",bridnum,bridge);}
codevs1002 搭桥