目录
1.题目描述
题意简写：给出两块彼此不连通的斑点，要求将这两块斑点连起来所需要涂的最少的点，涂点的时候只能沿着x方向和y方向来涂，并且只有对角线的斑点接触的时候不叫连通，只有xy其中一个方向的斑点紧靠在一起才叫联通。
2.题目思路
首先我们先来了解一下曼哈顿距离：两点之间的x坐标之差的绝对值加上y坐标值差的绝对值，数学表达式表述为
d(i,j)=|X1-X2|+|Y1-Y2|.
所以本题求的其实就是两块斑点集合中分别在两边取两点之间所有的曼哈顿距离的最小值
首先来看以下例子，假设构造出两块斑点，现在要涂上最少的格子使他们连通。蓝色和红色都表示奶牛原有的斑点，蓝色代表在两块集合中随机选中的两个点：
假设这两个蓝色方块之间的曼哈顿距离就是所需要涂的最短距离，现在我们构造一条曼哈顿路径，沿着黄色与黑色方块从左边的蓝色方块走到右边的黑色方块，如图：
这时我们发现，这个假设是不成立的，因为他的路径上出现了“障碍物”（黑色方块），这时我们可以很明显地看到黑色方块之间的曼哈顿距离更短，所以黑色方块之间的曼哈顿距离更有可能是涂的最少的路径选择。
现在我们来简化总结一下模型如图：
这就好比4个人走一条路，其中的两个人（黑色方块）在另外两个人（蓝色方块）的路径中间彼此靠近，那么正由于他们位于路径中间少走了一小段路，所以它们之间需要走的距离必然少于两个端点的人之间相互靠近所需要走的距离。
所以这个模型的本质就是：路径中间如果途径了障碍物，那必然存在比两起点之间曼哈顿距离更短的选择
所以我们返回这道题，这个模型推演的结果就是找出两个集合之间存在的最小曼哈顿距离
因此我们需要利用dfs或者bfs先将两个集合的斑点坐标保存下来，再暴力搜索两个集合，求出位于不同斑点集合中的每两个点之间的曼哈顿距离，取最小值。
为什么需要用dfs或者bfs，因为只有他们才能做到范围式的搜索，题中遇到 ‘ .’就必须停止搜索，从而避免了存储另外一个斑点块的数据，而顺序搜索很明显不能实现这一点。
3.dfs+求曼哈顿距离 c++题解
#include
#include
#include
using namespace std; int n, m; /*定义斑点整个图的行列大小*/ const int N = 55; char g[N][N];/*存储斑点整个图的集合*/ vector
>p[2]; /* p存储两个不连通的的斑点块的斑点点的坐标,一共有两个斑点块*/ int x[4] = { 0, 1, -1, 0 }, y[4] = { -1, 0, 0, 1 }; void dfs(int a, int b, vector
>&pp) /*深度优先遍历，将深度搜索到的两块斑点集合分别保存下来*/ { g[a][b] = '.'; /*这里采用的是不重复搜索的dfs，才能保证存储的集合点不重复*/ pp.push_back({ a, b }); for (int i = 0; i<4; i++) { int k = a + x[i],l = b + y[i]; /*对上下左右四个不同方向做dfs*/ if (k >= 0 && k
= 0 && l
> n >> m; for (int i = 0; i
> g[i]; /*输入奶牛斑点的数据图*/ for (int i = 0,k=0; i
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/222515.html原文链接：https://javaforall.net
![eclipse代码自动补全[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
