题目描述 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

题解：

关于题意，一定要注意所修的桥是只能沿着直线的，并且不限长度，一开始，在这里就让坑了。。。
对于第一问，我们只需要bfs一遍就求出来了，但是第二问真的很麻烦
因为要求最短边长和最少边数，那么就可以建边后跑最小生成树，用并查集来维护两个块是否联通。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int r, c, qsum = 0, qlen = 0, ans = 0, tot = 0;
int map[100][100];
char lsm[100][100];
int xx[5] = {0, 0, 0, 1, -1};
int yy[5] = {0, 1, -1, 0, 0};
int fa[23333];
struct qer
{
    int x, y;
};
struct edge
{
    int from, to, cost;
}es[233333];
queue <qer> q;
void build(int f, int t, int d)
{
    es[++tot] = (edge){f, t, d};
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool cmp(edge a, edge b)
{
    return a.cost < b.cost;
}
void bfs(int x, int y)
{
    while (!q.empty())
        q.pop();
    q.push((qer){x, y});
    map[x][y] = ans;
    while (!q.empty())
    {
        qer a = q.front();
        q.pop();
        for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++)
        {
            int lx = a.x + xx[i];
            int ly = a.y + yy[j];
            if (!xx[i]&&!yy[j])
                continue;
            if (lx < 1 || lx > r || ly < 1 || ly > c || map[lx][ly] != -1)
                continue;
            q.push((qer){lx, ly});
            map[lx][ly] = ans;
        }
    }
}
void deal()
{
    sort(es+1, es+tot+1, cmp);
    for (int i = 1; i <= tot; i++)
    {
        int x = es[i].from, y = es[i].to;
        if (find(x) != find(y))
        {
            fa[find(x)] = find(y);
            qlen += es[i].cost;
            // cout << es[i].from << " ceshi " << es[i].to << endl;
            qsum++;
        }
    }
}
void work(int x, int y)
{
    bool l = 0, r = 0;
    for (int i = 2; x + i <= r; i++)
    {
        int lx = x + i;
        if (y+1 <= c && map[lx][y+1] && map[lx][y+1] != map[x][y] && !l)
            build (map[lx][y+1], map[x][y], i-1), l = 1;
        if (y-1 >= 1 && map[lx][y-1] && map[lx][y-1] != map[x][y] && !r)
            build (map[lx][y-1], map[x][y], i-1), r = 1;
        if (map[lx][y] && map[lx][y] != map[x][y] && (!r || !l))
        {
            build (map[lx][y], map[x][y], i-1), r = 1, l = 1;
            break;
        }
    }
    l = 0, r = 0;
    for (int i = 2; x - i >= 1; i++)
    {
        int lx = x - i;
        if (y+1 <= c && map[lx][y+1] && map[lx][y+1] != map[x][y] && !l)
            build (map[lx][y+1], map[x][y], i-1), l = 1;
        if (y-1 >= 1 && map[lx][y-1] && map[lx][y-1] != map[x][y] && !r)
            build (map[lx][y-1], map[x][y], i-1), r = 1;
        if (map[lx][y] && map[lx][y] != map[x][y] && (!r || !l))
        {
            build (map[lx][y], map[x][y], i-1), r = 1, l = 1;
            break;
        }
    }
    l = 0, r = 0;
    for (int i = 2; y + i <= c; i++)
    {
        int ly = y + i;
        if (x+1 <= r && map[x+1][ly] && map[x+1][ly] != map[x][y] && !l)
            build (map[x+1][ly], map[x][y], i-1), l = 1;
        if (x-1 >= 1 && map[x-1][ly] && map[x-1][ly] != map[x][y] && !r)
            build (map[x-1][ly], map[x][y], i-1), r = 1;
        if (map[x][ly] && map[x][ly] != map[x][y] && (!r || !l))
        {
            build (map[x][ly], map[x][y], i-1), r = 1, l = 1;
            break;
        }
    }
    l = 0, r = 0;
    for (int i = 2; y - i >= 1; i++)
    {
        int ly = y - i;
        if (x+1 <= r && map[x+1][ly] && map[x+1][ly] != map[x][y] && !l)
            build (map[x+1][ly], map[x][y], i-1), l = 1;
        if (x-1 >= 1 && map[x-1][ly] && map[x-1][ly] != map[x][y] && !r)
            build (map[x-1][ly], map[x][y], i-1), r = 1;
        if (map[x][ly] && map[x][ly] != map[x][y] && (!r || !l))
        {
            build (map[x][ly], map[x][y], i-1), r = 1, l = 1;
            break;
        }
    }
}
void ceshi()
{
    puts("");
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            cout << map[i][j] << " ";
        }
        puts("");
    }
    for (int i = 1; i <= tot; i++)
        cout << es[i].from << " " << es[i].to << " " << es[i].cost << endl;
}
int main()
{
    for (int i = 1; i <= 20000; i++)
        fa[i] = i;
    cin >> r >> c;
    char a;
    for (int i = 1; i <= r; i++)
    for (int j = 1; j <= c; j++)
        cin >> lsm[i][j];
    for (int i = 1; i <= r; i++)
    for (int j = 1; j <= c; j++)
    {
        if (lsm[i][j] == '#')
            map[i][j] = -1;
        else
            map[i][j] = 0;
    }
    for (int i = 1; i <= r; i++)
    for (int j = 1; j <= c; j++)
    {
        if (map[i][j] == -1)
            ans++, bfs(i, j);
    }
    cout << ans << endl;
    for (int i = 1; i <= r; i++)
    for (int j = 1; j <= c; j++)
    {
        if (map[i][j])
        {
            work(i, j);
        }
    }
    deal();
    cout << qsum << " " << qlen;
    // ceshi();
    return 0;
}
/*
4 5
#.#.#
.###.
..#..
#.#.#
36 11
#.....##...
#.......##.
#.......#.#
#...#....#.
##.#...#..#
....####...
..#...#.##.
..........#
.##.#......
.#..#..#..#
#.####.#...
#..##.#....
.#..#.....#
#......####
...#.......
...#......#
#........#.
..#.#.#..##
......##.#.
...##....#.
#.#.....#..
##.#......#
##..#.#.#.#
.###.##....
........###
.##.#...#..
#.#.#.#....
...#.#..#..
....#..#.##
...#.#..#..
......####.
#.......##.
..##......#
#...###..#.
.......#...
....##.....
*/