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

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

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

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

1≤N,M≤50

### 输入样例：

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

### 输出样例：

``````3
``````

### 写法一：

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

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

### 写法二：

``````#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.

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

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

TODO