AcWing 2060. 奶牛选美
原题链接
中等
作者:
cylove
,
2024-04-18 21:29:09
,
所有人可见
,
阅读 4
暴力枚举俩个联通块每个点之间的曼哈顿距离求全局最小即可
#include <bits/stdc++.h>
using namespace std ;
const int N = 55 ;
char g[N][N] ;
bool st[N][N] ;
int indx[4] = {-1 , 0 , 0 , 1} , indy[4] = {0 , -1 , 1 , 0} ;
int n , m ;
std::vector<pair<int , int>> bfs(int x,int y) {
queue<pair<int , int>> que ;
que.push({x , y}) ;
st[x][y] = true ;
std::vector<pair<int , int>> C;
C.push_back({x , y}) ;
while (!que.empty()) {
auto p = que.front() ; que.pop() ;
for(int k = 0 ; k < 4 ; ++ k) {
int nx = p.first + indx[k] , ny = p.second + indy[k] ;
if ( nx >= 1 && nx <= n && ny >= 1 && ny <= m && !st[nx][ny] && g[nx][ny] == 'X')
{
st[nx][ny] = true ;
C.push_back({nx , ny}) ;
que.push({nx , ny}) ;
}
}
}
return C ;
}
int main()
{
cin >> n >> m ;
for(int i = 1 ; i <= n ; ++ i) cin >> g[i] + 1 ;
std::vector<pair<int , int>> a[2] ;
int ok = 0 ;
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j)
if ( !st[i][j] && g[i][j] == 'X' )
{
a[ok] = bfs(i , j) ;
ok ^= 1 ;
}
int ret = 0x3f3f3f3f ;
for(auto p : a[0])
for(auto q : a[1])
ret = min(ret , abs(p.first - q.first) + abs(p.second - q.second) - 1 ) ;
cout << ret << '\n' ;
return 0 ;
}