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