水儿的绘画——dfs连通块+暴力枚举

听说最新的流行趋势绘画册是一张图画上有两片连续图案， 水儿画了一大堆
两片图案的图画。 不幸的是， 时尚潮流往往变化很快， 而且最流行的时尚变成是
只有一片图案的图画！
水儿想让她的画更时尚， 把她的每一幅画挂在在墙上， 想把两片连续图案合
为一片图案的方法。 水儿的画用 N 乘 M（1<=N， M<=50） 的字符网格表示， 如下所
示：
. . . . . . . . . . . . . . . .
. . XXXX. . . . XXX. . .
. . . XXXX. . . . XX. . .
. XXXX. . . . . . XXX. .
. . . . . . . . XXXXX. . .
. . . . . . . . . XXX. . . .

这里， 每个“X” 表示一片图案的一部分。 两个 X 属于同一片图案,条件是如
果它们是垂直或水平相邻的（对角线相邻则不是） ， 所以上面的图画正好有两片
图案。 水儿所有的画都正好有两片图案。
水儿想用尽可能少的颜料把这两片图案合并成一大片图案。 在上面的例子中，
他可以画三个带有“X” 的附加字符（新字符用“” 标记， 以便于查看） 。
. . . . . . . . . . . . . . . .
. . XXXX. . . . XXX. . .
. . . XXXX. . . XX. . .
. XXXX. . **. . XXX. .
. . . . . . . . XXXXX. . .
. . . . . . . . . XXX. . . .

请帮助水儿确定她必须画的新“X” 的最小数量,把两片图案合并成一大片图案。
【输入】
第 1 行： 两个整数 N,M,用一个空格隔开；
第 2～N+1 行:每行是一个长度为 M 的， 由"X"和"."组成的字符串;
【输出】
共一行， 一个整数， 表示必须添加到输入图案中的新“X” 的最小数目。
【样例】

分析

1. 此题要利用连通块知识，那就dfs去搜索，把所到之处全标记为无法访问（可以采用vis数组标记，也可以直接将 ‘X’ 修改为 ‘.’ ）；因为从某一个点开始搜索，把所到之处全标记为无法访问，然后从这个点dfs结束后，那么就确定了一个连通块；
2. 此题有多种扩展，可以求连通块的块数，可以求连通块中最大的数量；此题是求连通两个连通块的最短距离，由于新铺的路要求是垂直或水平相邻的（对角线相邻则不是），所以我们可以发现连通两个点，需要水平方向，然后垂直方向铺路连通起来，也可以先垂直方向再水平方向；
3. 我们可以枚举一个连通块的所有点到另一个连通块所有点，然后取所有情况中，需要添加‘X’个数的最小值；然后(x,y)到(i,j)需要铺的‘X’的块数是：|x-i| + |y-j| - 1（水平的差值+竖直方向的差值 - 共同的一个点）

#include

using namespace std;

struct node {
    int x, y;
};

int n, m, cnt, ans = 100000;
char a[55][55];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
//数组类型为vector的数组，v[0]就是一个容器
vector<node> v[2];//存放两个连通块的所有坐标

void dfs(int x, int y) {
	//走过的点不用走了
    a[x][y] = '.';
    node no;
    no.x = x, no.y = y;
    //将这个点放在第cnt个连通块里面
    v[cnt].push_back(no);
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 0 && yy >= 0 && xx <= n && yy <= m && a[xx][yy] == 'X') {
            dfs(xx, yy);
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //每搜一圈结束就是一个连通块
            if (a[i][j] == 'X') {
                dfs(i, j);
                cnt++;//连通块数
            }
        }
    }
    //枚举任意两个点
    for (int i = 0; i < v[0].size(); i++) {
        for (int j = 0; j < v[1].size(); j++) {
            ans = min(ans, abs(v[0][i].x - v[1][j].x) + abs(v[0][i].y - v[1][j].y) - 1);
        }
    }
    cout << ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

不知道这个题哪里有可以提交的oj，就测试了个样例；