AcWing 2060. 奶牛选美
原题链接
中等
作者:
a行君
,
2024-04-09 22:56:30
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
using namespace std;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 52;
bool md[N][N],d[N][N];
int n,m;
using T = pair<int, int>;
vector<T> block[2];
void dfs(int idx,int x,int y){
d[x][y]=true;
block[idx].push_back({x,y});
for (int i = 0; i < 4; i ++ ){
int dxx = dx[i]+x,dyy = dy[i]+y;
if(dxx>n||dyy>m||d[dxx][dyy]||dxx<=0||dyy<=0||!md[dxx][dyy])continue;
dfs(idx,dxx,dyy);
}
}
void show(){
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= m; j ++ ){
cout<<md[i][j]<<" ";
}
cout << endl;
}
}
int main()
{
cin >> n>>m;
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= m; j ++ ){
char t;
cin >> t;
if(t=='X')md[i][j]=true;
}
}
int idx = 0;
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= m; j ++ ){
if(!d[i][j]&&md[i][j]){
dfs(idx++,i,j);
/// show();
}
}
}
int ans = 1e8;
for(int i = 0;i<block[0].size();i++){
for (int j = 0; j < block[1].size(); j ++ ){
ans = min(ans,abs(block[0][i].first-block[1][j].first)+abs(block[0][i].second-block[1][j].second));
}
}
cout << ans-1;
}