【题目来源】
【题目描述】
听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。
不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。
牛皮可用一个 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 和 . 构成的字符串，用来表示描述牛皮图案的字符矩阵。
【输出格式】
输出需要涂色区域的最少数量。
【输入样例】
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....【输出样例】
3
【数据范围】
1≤N,M≤50
【算法分析】
● Flood Fill 是一种用于填充/标记连通区域的算法，常用于图像处理、游戏开发等领域。它可以通过 BFS（广度优先搜索） 或 DFS（深度优先搜索） 来实现。
● “AcWing 2060：奶牛选美”的本质，其实就是求两个连通块之间的最短曼哈顿距离。
由于数据量比较小（最多有 50×50=2500 个点）,所以我们完全可以将两个连通块的点存下来，
再暴力循环求出最短曼哈顿距离（O(n ^ 2)）。
【算法代码】
#include <bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;
vector<PII> v1,v2;
const int N=55;
char g[N][N];
bool st[N][N];
int dx[]= {-1,0,1,0},dy[]= {0,1,0,-1};
int n,m;void bfs(int x,int y,int cnt) {st[x][y]=true;queue<PII> q;q.push({x,y});while(q.size()) {PII t=q.front();q.pop();if(cnt==1) v1.push_back({t.first,t.second});else v2.push_back({t.first,t.second});for(int i=0; i<4; i++) {int tx=t.first+dx[i],ty=t.second+dy[i];if(tx<0 || tx>=n || ty<0 || ty>=m) continue;if(g[tx][ty]=='.' || st[tx][ty]) continue;st[tx][ty]=true;q.push({tx,ty});}}
}int main() {cin>>n>>m;for(int i=0; i<n; i++) cin>>g[i];int cnt=1;for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {if(g[i][j]=='X' && !st[i][j]) {bfs(i,j,cnt);cnt++;}}}int ans=INT_MAX;for(auto p1:v1) {for(auto p2:v2) {int t=abs(p1.first-p2.first)+abs(p1.second-p2.second);ans=min(ans,t);}}cout<<ans-1<<endl;return 0;
}/*
in:
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....out:
3
*/
【参考文献】