codevs——1002 搭桥

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

 

 

 

题目描述 

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

 

代码：

#include 
          
           #include 
           
            using namespace std;#define maxn 100000int xx[8]={
        0,0,1,1,1,-1,-1,-1},yy[8]={
        1,-1,0,1,-1,0,1,-1};int n,m,q[1005][1005],dad[maxn],cnt,ans,sum;bool map[1005][1005];struct node{
        int x,y,v;}e[maxn];bool cmp(node a,node b){
        return a.v
            
             n||y2<1||y2>m||!q[x2][y2])return 1;    if(q[x1][y1]==q[x2][y2])return 0;    cnt++;    e[cnt].x=q[x1][y1];    e[cnt].y=q[x2][y2];    e[cnt].v=t-1;    return 1;}void dfs(int x,int y){    q[x][y]=ans;    for(int i=0;i<8;i++){        int x0=x+xx[i],y0=y+yy[i];        if(map[x0][y0]&&!q[x0][y0])dfs(x0,y0);    }}void build(int x,int y){    for(int i=x+1;i<=n;i++)      if(!input(x,y,i,y,i-x)||!input(x,y,i,y+1,i-x)||!input(x,y,i,y-1,i-x))break;    for(int i=x-1;i>0;i--)      if(!input(x,y,i,y,x-i)||!input(x,y,i,y+1,x-i)||!input(x,y,i,y-1,x-i))break;    for(int i=y+1;i<=m;i++)      if(!input(x,y,x,i,i-y)||!input(x,y,x+1,i,i-y)||!input(x,y,x-1,i,i-y))break;    for(int i=y-1;i>0;i--)      if(!input(x,y,x,i,y-1)||!input(x,y,x+1,i,y-i)||!input(x,y,x-1,i,y-i))break;  }void work1(){    ans=0;    for(int i=1;i<=n;i++)      for(int j=1;j<=m;j++)        if(map[i][j]&&!q[i][j]){ans++;dfs(i,j);}    cout<
             
              <
              
               >n>>m;    for(int i=1;i<=n;i++)      {          char a[maxn];          cin>>a;          for(int j=1;j<=m;j++)          if(a[j-1]=='#')map[i][j]=1;      }    work1();    work2();    return 0;}