acwing-2060. 奶牛选美

2023-10-25 17:37:22

听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。
不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。
牛皮可用一个 N×M 的字符矩阵来表示，如下所示：

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

其中，X 表示斑点部分。
如果两个 X 在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。
约翰牛群里所有的牛都有两个斑点。
约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。
在上面的例子中，他只需要给三个 .. 区域内涂色即可（新涂色区域用 ∗ 表示）：

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....

请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。

输入格式

第一行包含两个整数 N 和 M。

接下来 N 行，每行包含一个长度为 M 的由 X 和 . 构成的字符串，用来表示描述牛皮图案的字符矩阵。

输出格式

输出需要涂色区域的最少数量。

数据范围

1≤N,M≤50

输入样例：

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

输出样例：

方法一：遍历两个斑点的所有可能距离

先分别用两个vector存两个斑点上的所有点，遍历点上的所有曼哈顿距离（|x1-x2|+|y1-y2|），取最小值

写法一：

一开始还没理清思路，写下了这个乐色写法：先BFS找到一个斑点上的其中一个点，再BFS从该点找到该斑点，再遍历矩阵找到另一个斑点，最后遍历计算曼哈顿距离

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int x{}, y{};

    Node(int x, int y) {
        this->x = x;
        this->y = y;
    }

    Node() = default;;
};

string matrix[51];
bool flag[51][51];
int n, m;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void pushAdj(queue<Node> &q, Node &node) {
    for (int i = 0; i < 4; i++) {
        int a = node.x + dx[i], b = node.y + dy[i];
        if (a >= 0 && a < m && b >= 0 && b < n && !flag[b][a]) {
            q.emplace(a, b);
            flag[b][a] = true;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        cin >> matrix[i];

    // 寻找其中一个斑点
    Node node;
    memset(flag, 0, sizeof(flag));
    flag[0][0] = true;
    queue<Node> q;
    q.push(Node(0, 0));
    while (!q.empty()) {
        node = q.front();
        q.pop();
        if (matrix[node.y][node.x] == 'X') break;
        pushAdj(q, node);
    }
    while (!q.empty()) q.pop();

    // 获取两个斑点
    vector<Node> dot1, dot2;
    memset(flag, 0, sizeof(flag));
    q.push(node);
    while (!q.empty()) {
        node = q.front();
        q.pop();
        if (matrix[node.y][node.x] == 'X') {
            matrix[node.y][node.x] = 'a';
            dot1.emplace_back(node.x, node.y);
            pushAdj(q, node);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            if (matrix[i][j] == 'X') dot2.emplace_back(j, i);
    }

    // 计算最短距离
    int res = INT_MAX;
    for (const auto &d1 : dot1) {
        for (const auto &d2 : dot2)
            res = min(res, abs(d1.x - d2.x) + abs(d1.y - d2.y));
    }

    printf("%d", res-1);

    return 0;
}

写法二：

为了省去BFS带来的麻烦，使用DFS，在visit结点时，如果是'X'就入队。最终得到两个连通分量points[0]和[1]，遍历计算曼哈顿距离

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
string matrix[51];
int n, m;
vector<pii> points[2];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void dfs(int x, int y, vector<pii> &point) {
    point.emplace_back(x, y);
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < m && matrix[a][b] == 'X') {
            matrix[a][b] = '.';
            dfs(a, b, point);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> matrix[i];

    int k = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            if (matrix[i][j] == 'X')
                dfs(i, j, points[k++]);
    }

    int res = INT_MAX;
    for (const auto &d1 : points[0]) {
        for (const auto &d2 : points[1])
            res = min(res, abs(d1.first - d2.first) + abs(d1.second - d2.second));
    }
    cout << res - 1;
}

方法二：双端队列

TODO

码农公寓