2060. 奶牛选美 - AcWing题库
yxc代码AcWing 2060. 奶牛选美 - AcWing
题意:上下左右连通的点X被看做一个连通块,现在有两个连通块,求两个连通块的最小曼哈顿距离
P(xP,yP),Q(xQ,yQ)两点间的曼哈顿距离的计算方法：
Manhattan(P,Q)=|xP?xQ|+|yP?yQ|
思路:dfs找出两个连通块包含的点,然后分别枚举两个连通块各点 到另外连通块点的曼哈顿距离,取最小值
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=55;
int n,m;
char g[N][N];
vector<PII> points[2];
int dx[4]={-1,0,0,1},dy[4]={0,1,-1,0};
void dfs(int x,int y,vector<PII>& ps)
{g[x][y]='.';ps.push_back({x,y});for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]=='X'){dfs(a,b,ps);}}
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++) cin>>g[i];for(int i=0,k=0;i<n;i++){for(int j=0;j<m;j++){if(g[i][j]=='X'){dfs(i,j,points[k++]); }}}int res=1e8;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<<endl;return 0;
}