Floodfill染色,加入后枚举即可,坑点,注意曼哈顿距离需双方同时取abs
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100;
char mp[N][N];
queue<pair<int, int>> q;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
vector<pair<int, int>> a, b;
int main()
{
int y, x;
cin >> y >> x;
for(int i = 1;i <= y;i ++)
for(int j = 1;j <= x;j ++)
cin >> mp[i][j];
int mark = 1,flag = 0;
for(int i = 1;i <= y;i ++)
for(int j = 1;j <= x;j ++){
if(mp[i][j] == 'X'){
q.push({i, j});
while(q.size()){
auto k = q.front();
q.pop();
if(mp[k.first][k.second] == 'X'){
a.push_back({k.first,k.second});
mp[k.first][k.second] = 0;
for(int i = 0;i < 4;i ++){
q.push({k.first + dy[i],k.second + dx[i]});
}
}
}
swap(a, b);
}
}
int res = 0x3f3f3f3f;
for(auto i : a)
for(auto j : b){
res = min(res, abs(i.first - j.first) + abs(i.second - j.second));
}
cout << res - 1;
}