搭桥

【题目描述】

有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。

【输入描述】

在输入的数据中的第一行包含描述城市的两个整数R和C，分别代表从北到南、从东到西的城市大小(1 <= R <= 50，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

源代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,Num,sum,ans,Mark[51][51],F[2001]={0};
bool Map[51][51]={0};
int x[8]={0,0,1,1,1,-1,-1,-1},y[8]={1,-1,0,1,-1,0,1,-1};
struct Node
{
    int X,Y,V;
}i[100001];
bool Rule(Node t1,Node t2) //稀奇了，如果有"&"还得加"const"。
{
    return t1.V<t2.V;
}
int Find(int t)
{
    return !F[t]?t:F[t]=Find(F[t]);
}
bool Insert(int X1,int Y1,int X2,int Y2,int V)
{
    if (Y2<1||Y2>m||X2<1||X2>n||!Mark[X2][Y2]) //越界或空白就跳回。
      return true;
    if (Mark[X1][Y1]==Mark[X2][Y2]) //同一个建筑物。
      return false;
    Num++; //总桥梁数。
    i[Num].X=Mark[X1][Y1];
    i[Num].Y=Mark[X2][Y2];
    i[Num].V=V-1; //线段的长度与端点。
    return true;
}
int DFS(int t1,int t2)
{
    Mark[t1][t2]=ans;
    for (int a=0;a<8;a++)
    {
        int T1=t1+x[a];
        int T2=t2+y[a];
        if (Map[T1][T2]&&!Mark[T1][T2])
          DFS(T1,T2);
    }
}
void Work1()
{
    ans=0;
    for (int a=1;a<=n;a++)
      for (int b=1;b<=m;b++)
        if (Map[a][b]&&!Mark[a][b]) //Mark[i][j]存储着(i,j)的所属建筑物编号。
        {
            ans++;
            DFS(a,b);
        }
    printf("%d
",ans);
}
void Build(int t1,int t2)
{
    for (int a=t1+1;a<=n;a++) //下。
      if (!Insert(t1,t2,a,t2,a-t1)||!Insert(t1,t2,a,t2+1,a-t1)||!Insert(t1,t2,a,t2-1,a-t1)) //再往下会死人的！
        break;
    for (int a=t1-1;a>0;a--) //上。
      if (!Insert(t1,t2,a,t2,t1-a)||!Insert(t1,t2,a,t2+1,t1-a)||!Insert(t1,t2,a,t2-1,t1-a))
        break;
    for (int a=t2+1;a<=m;a++) //右。
      if (!Insert(t1,t2,t1,a,a-t2)||!Insert(t1,t2,t1-1,a,a-t2)||!Insert(t1,t2,t1+1,a,a-t2))
        break;
    for (int a=t2-1;a>0;a--) //左。
      if (!Insert(t1,t2,t1,a,t2-a)||!Insert(t1,t2,t1-1,a,t2-a)||!Insert(t1,t2,t1+1,a,t2-a))
        break;
}
void Work2()
{
    for (int a=1;a<=n;a++)
      for (int b=1;b<=m;b++)
        if (Map[a][b])
          Build(a,b); //为后面的Kruskal算法做预处理。
    sort(i+1,i+Num+1,Rule); //Kruskal算法求最小生成树。
    ans=0;
    for (int a=1;a<=Num;a++)
    {
        int t1=Find(i[a].X);
        int t2=Find(i[a].Y);
        if (t1!=t2)
        {
            F[t1]=t2;
            ans++;
            sum+=i[a].V;
        }
    }
    printf("%d %d
",ans,sum);
}
int main()
{
    scanf("%d%d",&n,&m);
/* 我就不明白了，为啥差别咋就这么大呢。

    for (int a=1;a<=n;a++)
    {
        char T=getchar();
        for (int b=1;b<=m;b++)
        {
            T=getchar();
            if (T=='#')
              Map[a][b]=true;
        }
    }

*/
    for (int a=1;a<=n;a++) //坑爹的读入。
    {
        char T[51];
        scanf("%s",T);
        for (int b=1;b<=m;b++)
          if  (T[b-1]=='#')
            Map[a][b]=true;
    }
    Work1(); //建筑物数量。
    Work2(); //桥的数量与总长度。
    return 0;
}

/*
    解法：
        第一问DFS即可，第二问先将所有能连起来的建筑物都连起来，再从中找最小生成树。
    反思教训：
        问题要学会灵活转化及多角度看待，遇到麻烦要努力解决而不是停滞不前。
*/