最少联通代价【曼哈顿距离】

本文主要是介绍最少联通代价【曼哈顿距离】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

思路简析

法一：先用一个小深搜区分出两个连通块的点，再用广搜搜出每个连通块1的点到每个连通块2的点上的距离，每次用min()更新最小值。
代码实现如下（找的一位Pal帮忙打的，还是有点儿良心特此声明）：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,pre[1000000],a[1000000],b[1000000],minn,ans=1e10;
int x[4]={1,-1,0,0},y[4]={0,0,1,-1};
char map[100][100];
bool mark[100][100];
bool check(int s,int t)
{if(s&&t&&s<=n&&t<=m&&!mark[s][t]&&map[s][t]!='S') return 1;return 0;
}
void fun(int d)
{minn++;if(pre[d]) fun(pre[d]);
}
void bfs(int r,int c)
{memset(mark,0,sizeof(mark));minn=0;int head=0,tail=1;int nextr,nextc;mark[r][c]=1;pre[1]=0;a[1]=r;b[1]=c;while(head!=tail){head++;for(int i=0;i<4;i++){nextr=a[head]+x[i];nextc=b[head]+y[i];if(check(nextr,nextc)){tail++;a[tail]=nextr;b[tail]=nextc;mark[nextr][nextc]=1;pre[tail]=head;if(map[nextr][nextc]=='X'){fun(tail);ans=min(minn,ans);}}}}
}
void dfs(int r,int c)
{for(int i=0;i<4;i++)if(check(r+x[i],c+y[i])&&map[r+x[i]][c+y[i]]!='.'){mark[r+x[i]][c+y[i]]=1;map[r+x[i]][c+y[i]]='S';dfs(r+x[i],c+y[i]);mark[r+x[i]][c+y[i]]=0;}
}
void f()
{for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(map[i][j]=='X'){dfs(i,j);map[i][j]='S';return ;}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",map[i]+1);bool flag=1;f();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(map[i][j]=='S')bfs(i,j);printf("%d",ans-2);
}

法二：也同样用一个小深搜，记录下两个连通块分别的各自坐标，再用曼哈顿距离的思想枚举每个连通块1上的点到每个连通块2上的点上的距离，求出最小值。
干货：详解曼哈顿距离及其代替广搜的原因
但这道题应是曼哈顿距离-1，因为它并不是要求路径步数，而是求联通代价，当距离第二个连通块还剩一步的时候，就已经达成目标了，不用走到第二个连通块上去，所以要少一步。
代码实现如下：

#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
char a[55][55];//存“地图”
int n,m/*长、宽*/,ans=1e8/*顾名思义*/,xx[4]={-1,0,0,1},yy[4]={0,-1,1,0}/*移动方向*/,s/*表示现在搜到的是第几个连通块*/;
struct node{int x1,y1;
}temp;//结构体记录下坐标，temp用来将坐标存入结构体，放进数组
vector<node>f[2];//由于不确定连通块1、2分别有多少个点，所以用动态数组存储//其实很简单，待会儿结尾放一个超链接
void dfs(int x, int y)
{a[x][y]='.';//避免重复搜索temp.x1=x;temp.y1=y;f[s].push_back(temp);//记录坐标，放进数组里for(int i=0;i<4;i++)//拓展四周联通的连通块点做处理{int fx=x+xx[i],fy=y+yy[i];if(fx>=0&&fx<n&&fy>=0&&fy<m&&a[fx][fy]=='X')dfs(fx,fy);}
}
int main()
{scanf("%d %d",&n,&m);for(int i=0;i<n;i++)scanf("%s",a[i]);//读取一行字符
/*忽然想到补充一点，如果从[1]开始的话，应该这么写：for(int i=1;i<=n;i++)scanf("%s",a[i]+1);a[i]就是地址，+1就是往后一个存（数组的地址是连续的）
*/for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(a[i][j]=='X')//搜到一个连通块{dfs(i,j);s++;//连通块+1}for(int i=0;i<f[0].size();i++)for(int j=0;j<f[1].size();j++)ans=min(ans,int(fabs(f[0][i].x1-f[1][j].x1)+fabs(f[0][i].y1-f[1][j].y1)-1));//利用曼哈顿距离思想求解printf("%d",ans);return 0;
}