AcWing 2060. 奶牛选美
原题链接
中等
作者:
Dovir
,
2024-04-05 23:01:46
,
所有人可见
,
阅读 5
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 60;
char matrix[N][N];
int state[N][N];
int dx[4] = {1, -1, 0, 0};//上下左右扩展偏移量
int dy[4] = {0, 0, 1, -1};
int n, m, flag = 1;
void bfs(int a, int b){
queue<pair<int, int>> q;
q.push({a, b});
state[a][b] = flag;
while(q.size()){
pair<int, int> tmp = q.front();
q.pop();
for(int i = 0; i < 4; i++){//对上下左右四个方向进行搜索
int x = tmp.first + dx[i];
int y = tmp.second + dy[i];
if(x < 1 || x > n || y < 1 || y > m){//出界不合法不扩展
continue;
}
if(state[x][y] != 0){//遍历过不合法
continue;
}
if(matrix[x][y] != 'X'){//不是斑点不做扩展
continue;
}
q.push({x, y});//将合法的斑点坐标入队列
state[x][y] = flag;//将斑点进行标记(flag初始值为1)
}
}
flag++;//下一次遍历连通块flag将变成2,用2标记第二个斑点
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> matrix[i] + 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(matrix[i][j] == 'X' && state[i][j] == 0){
bfs(i, j);
}
}
}
int res = 999;
for(int x1 = 1; x1 <= n; x1++){//暴力枚举所有被标记为1的点
for(int y1 = 1; y1 <= m; y1++){
if(state[x1][y1] == 1){
for(int x2 = 1; x2 <= n; x2++){//暴力枚举所有被标记为2的点
for(int y2 = 1; y2 <= m; y2++){
if(state[x2][y2] == 2){
int len = abs(x1 - x2) + abs(y1 - y2);//求两点之间的曼哈顿距离
res = min(res, len);//更新最短路径
}
}
}
}
}
}
cout << res - 1 << endl;
return 0;
}