最少联通代价(dfs+曼哈顿距离)

#include <bits/stdc++.h>
#define maxn 55
#define inf 0x3f3f3f3f
using namespace std;
char pre[maxn][maxn];
struct Node{
	int x,y;
}Edge;
vector<Node> v[2];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int n,m,s;

bool Check(int x,int y){
	if(x >= 0 && y >= 0 && x < n && y < m && pre[x][y] == 'X')return true;
	return false;
}

void dfs(int x,int y){
	pre[x][y] = '.';
	Edge.x = x;
	Edge.y = y;
	v[s].push_back(Edge);
	for(int i=0;i<4;i++){
		int xx = x + dir[i][0];
		int yy = y + dir[i][1];
		if(Check(xx, yy)){
			dfs(xx, yy);
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",pre[i]);
	}
	s = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(pre[i][j] == 'X'){
				dfs(i,j);
				s ++;
			}
		}
	}
	int ans = inf;
	for(int i=0;i<v[0].size();i++){
		for(int j=0;j<v[1].size();j++){
			ans = min(ans, abs(v[0][i].x - v[1][j].x) + abs(v[0][i].y - v[1][j].y) - 1);
		}
	}
	printf("%d\n",ans);
	return 0;
}