题目描述
给你一个二维的字符矩阵,矩阵上有X
和.
,X
表示此处有颜色,.
表示此处没有颜色,我们把两个在垂直方向或者水平方向相邻的点表示为一个色块,此二维矩阵内有两个色块,请你给出将最少多少个.
涂抹为X
,使得两个色块合为一个色块。
算法1:Flood Fill+DFS
要使两个色块联通,则两个色块一定有两个点在垂直方向或者水平方向相邻,要涂抹最少的点,一定要找两个色块中离得最近的两个点,将两个点中间的点涂抹。要知道两个点离得距离,我们可以使用曼哈顿距离来计算。
我们可以使用DFS分别把两个色块的点存到两个数组中,再分别求两个数组中曼哈顿距离最近的点的距离,就是答案。
思路
- 输入字符矩阵
- 将
X
的坐标分别存到两个数组- 循环字符矩阵
- 第一次遇到
X
时,dfs所有与该点相邻的点,并将位置放入第一色块数组,并将字符矩阵该点改为.
- 第二次遇到
X
时,dfs所有与该点相邻的点,并将位置放入第二色块数组,并将字符矩阵该点改为.
- 第一次遇到
- 循环字符矩阵
- 循环第一个色块数组中的点
- 循环第二个色块数组中的点
- 计算两个点的曼哈顿距离,取答案
- 循环第二个色块数组中的点
- 输出答案
注意点
- 曼哈顿距离最后要减一
C++
代码
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 55;
int n, m;
char g[N][N];
vector<pair<int, int> > points[2];
int dx[] = {- 1, 1, 0, 0}, dy[] = {0, 0, 1, - 1};
void dfs(int x, int y, vector<pair<int, int> > &q) {
g[x][y] = '.';
q.push_back({x, y});
for ( int i = 0; i < 4; ++ i ) {
int xx = x + dx[i], yy = y + dy[i];
if ( xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] == 'X' ) {
dfs(xx, yy, q);
}
}
}
int main() {
cin >> n >> m;
for ( int i = 0; i < n; ++ i ) cin >> g[i];
bool first = true;
for ( int i = 0; i < n; ++ i ) {
for ( int j = 0; j < m; ++ j ) {
if ( g[i][j] == 'X' ) {
if ( first ) {
first = false;
dfs(i, j, points[0]);
} else {
dfs(i, j, points[1]);
}
}
}
}
int res = INT_MAX;
for ( auto a: points[0] ) {
for ( auto b: points[1] ) {
res = min(res, abs(a.x - b.x) + abs(a.y - b.y) - 1);
}
}
cout << res << '\n';
return 0;
}
参考文献
AcWing 2060. 奶牛选美 (bfs+暴力枚举) - AcWing
题目链接
算法标签
DFS(深度优先搜索) Flood Fill