acwing-2060. 奶牛选美(acwing-2060. Cow beauty pageant)

听说最近两斑点的奶牛最受欢迎,约翰立即购进了一批两斑点牛。
不幸的是,时尚潮流往往变化很快,当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色,使得它们身上的两个斑点能够合为一个斑点,让它们能够更加时尚。
牛皮可用一个 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....

输出样例:

3

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

先分别用两个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

————————

Hearing that the two spotted cows were the most popular recently, John immediately bought a batch of two spotted cows.
Unfortunately, fashion trends often change quickly, and the most popular cow has become a spotted cow.
John hopes that by coloring each cow, the two spots on their body can be combined into one spot, so that they can be more fashionable.
One n is available for cowhide × M, as shown below:

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

Where X represents the speckle part.
If two X’s are adjacent in the vertical or horizontal direction (diagonal adjacency is not included), they belong to the same spot, so it can be seen that there are exactly two spots in the above figure.
All the cows in John’s herd have two spots < / strong >.
John hopes to combine the two spots by using paint to color as few areas as possible.
In the above example, he only needs to give three Just paint in the area (the newly painted area is indicated by):

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

Please help John determine the minimum number of areas he needs to paint in order to combine the two spots into one.

Input format

The first line contains two integers n and m.

Next, n rows, each containing an X and X of length M The character string is used to represent the character matrix describing the cowhide pattern.

Output format

Output the minimum number of areas to be colored.

Data range

1≤N,M≤50

Input example:

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

Output example:

3

Method 1: traverse all possible distances between two spots

First, save all points on the two spots with two vectors, traverse all Manhattan distances (|x1-x2| + |y1-y2|) on the points, and take the minimum value

Writing method 1:

At the beginning, I didn’t clear my mind and wrote down this happy writing method: first BFS found one of the points on a spot, then BFS found the spot from that point, then traversed the matrix to find another spot, and finally traversed to calculate the Manhattan distance

#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;
}

Method 2:

In order to save the trouble caused by BFS, DFS is used to join the team if it is’ x ‘at the visit node. Finally, two connected components points [0] and [1] are obtained to traverse and calculate the Manhattan distance

#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;
}

Method 2: double ended queue

TODO