AcWing 2060. 奶牛选美 (DFS 枚举)

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;
}