题目描述
把两斑点奶牛变成一斑点奶牛
思路&&重点
就是把两个连通块合并为一个连通块
类似于”全球变暖”的题目,先求连通块。用dfs算法求。
这种求用dfs求连通块的题目,只要某个连通块的任意一个点被dfs()了,整个连通块的点都会被遍历到。所以其实只要dfs两次(最外层的),每次一个连通块,放在两个vector里面。
这里关于dfs的方式,别认为它是一条类似于直线的路线,一直走,它的实际路线也是向四周扩散的。
最后一步就是在两个连通块里面找点,求两点的距离最短的,这里的距离指的不是直接连线的距离,因为不能斜着走,只能上下左右,所以一个点到另一个点的最短距离是哈弗曼顿距离,就是x差值的绝对值加y差值的绝对值最小的。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
const int N=55;
int n,m;
char a[N][N];
vector<pii>p[2];//这里可以看成是二维的 p[0]就是一个容器 p[1]是另一个容器
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y,vector<pii>&q)//这里的&q是引用类型 就是不用复制 运行效率高
{
q.push_back({x,y});//先放到一个vector中去
a[x][y]='.';//设置为. 表示访问过了
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=0 && xx<n && yy>=0 && yy<m && a[xx][yy]=='X')
{
dfs(xx,yy,q);
}
}
return;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) scanf("%s",a[i]);
for(int i=0,k=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(a[i][j]=='X') dfs(i,j,p[k++]);//找到了符合的点就dfs
}//k是0开始 表示vector p[0]
int ans=100000;
for(auto&i : p[0])//遍历一个vector i 就是其中元素的值 不是下标
for(auto&j : p[1])
{
ans=min(ans,abs(i.first-j.first)+abs(i.second-j.second));
}
cout<<ans-1;//算之间点的数量 ans是距离
return 0;
}