最少联通代价【曼哈顿距离】
Description
在一个 N 行 M 列的字符网格上， 刚好有 2 个彼此分开的连通块。每一个连通 块的一个格点与它的上、下、左、右的格子连通。以下图所示：
如今要把这 2 个连通块连通， 求最少须要把几个’.’转变成’X’。上图的例子中， 最少只须要把 3个’.’转变成’X’。下图用’*’表示转化为’X’的格点。
Input
第 1 行：2 个整数 N 和 M(1<=N,M<=50) 接下来 N 行，每行 M 个字符， ’X’表示属于某个连通块的格点，’.’表示不属于某 个连通块的格点web
Output
第 1 行：1 个整数，表示最少须要把几个’.’转变成’X’数组
Sample Input
6 16
…………….
..XXXX….XXX…
…XXXX….XX…
.XXXX……XXX..
……..XXXXX…
………XXX….svg
Sample Output
3ui
思路简析
法一：先用一个小深搜区分出两个连通块的点，再用广搜搜出每一个连通块1的点到每一个连通块2的点上的距离，每次用min()更新最小值。
代码实现以下（找的一位Pal帮忙打的，仍是有点儿良心特此声明）：spa
#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，由于它并非要求路径步数，而是求联通代价，当距离第二个连通块还剩一步的时候，就已经达成目标了，不用走到第二个连通块上去，因此要少一步。
代码实现以下：.net
#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];//因为不肯定连通块一、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;
}