Description

在一个 N 行 M 列的字符网格上， 恰好有 2 个彼此分开的连通块。每个连通 块的一个格点与它的上、下、左、右的格子连通。如下图所示： 

现在要把这 2 个连通块连通， 求最少需要把几个’.’转变成’X’。上图的例子中， 最少只需要把 3个’.’转变成’X’。下图用’*’表示转化为’X’的格点。 

Input 

第 1 行：2 个整数 N 和 M(1<=N,M<=50) 接下来 N 行，每行 M 个字符， ’X’表示属于某个连通块的格点，’.’表示不属于某 个连通块的格点

Output 

第 1 行：1 个整数，表示最少需要把几个’.’转变成’X’

Sample Input 

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

Sample Output 

3

Hint

1<=N,M<=50

 

       这道题有两种做法，一种是先用dfs去区分两个连通块，然后再用bfs去跑两个连通块相连的最小值；另一种方法是运用了曼哈顿的思想，我们先用dfs去把每个连通块的坐标存起来，然后去遍历两个连通块的坐标的最小曼哈顿距离就好了。

       不得不说第二种方法角度刁钻思路惊奇...

Code：

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