自动搬运

查看原文

来自洛谷，原作者为

	qzhwlzy AFO

搬运于2025-08-24 22:17:44，当前版本为作者最后更新于2020-11-05 16:08:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送#1

传送#2

思路

解题过程主要可以分为2步：

1. 读入，将三个斑点依次编号为1,2,3，方法有很多，如 $dfs$ 或 $bfs$ ，这里不细讲了。
2. 关键步骤，我们知道，对于任意两个斑点，无非只有上图所示的两种情况，因此，我们需要分别计算两种情况改变的最小格子数（以下称为距离）。

• 第一种，将两个斑点连通至第三个斑点，需要我们分别记录每两个斑点之间的距离，一共就三种情况。
• 第二种，将三个斑点连至一个不在斑点上的点，我们就可以循环每一个不在斑点上的点，计算距离并求最小值。

计算过程

依次循环每一个点，如果是‘ $X$ ’，那么进行第一种操作；若为‘ $.$ ’，则进行第二种操作。

具体函数实现

• 曼哈顿距离

  曼哈顿距离(Manhattan distance or Manhattan length)或方格线距离是由十九世纪的赫尔曼·闵可夫斯基所创辞汇，为欧几里得几何度量空间的几何学之用语，用以标明两个点上在标准坐标系上的绝对轴距之总和。
  由以上 $bdfs$ 的结果我们可以知道，本题显然要用曼哈顿距离函数，此函数实现并不难，就是两点的横纵坐标差值和（我的C++出 $bug$ 了，不能用 $abs$ 函数，故代码中自己写了函数且没有单独定义曼哈顿距离函数）。

• 第一种操作
  第一种操作我写得比较暴力，直接循环每个点，如果不是同斑点的话，直接求它们的曼哈顿距离。

  for(int k=1;k<=n;k++){
   	for(int l=1;l<=m;l++){
   		if(a[k][l]==0){
   			continue;
   		}
   		if(a[k][l]!=a[i][j]&&dis[a[i][j]][a[k][l]]>abss(i-k)+abss(j-l)){
   			dis[a[k][l]][a[i][j]]=min(dis[a[k][l]][a[i][j]],abss(i-k)+abss(j-l));
   		}
   	}
   }
  

• 第二种操作
  第二种操作我单独写了函数，直接曼哈顿求某个不在任一斑点上的点到三个斑点的曼哈顿距离，总和最小即可。

  int xx[4];
  xx[1]=xx[2]=xx[3]=999999;
  for(int p=1;p<=n;p++){
  	for(int q=1;q<=m;q++){
  		if(x[p][q]=='X'){
  			xx[a[p][q]]=min(xx[a[p][q]],abss(i-p)+abss(j-q)-1);
  		}
  	}
  }	
  return xx[1]+xx[2]+xx[3]+1;
  

综上，大家可以看出我的代码的时间复杂度非常高，但是能卡过，建议自己找简单解法。

完整代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 55
using namespace std;
int n,m;
char x[maxn][maxn];
int a[maxn][maxn]={};
bool vis[maxn][maxn];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int f[5][5],tot=0;
int dis[4][4],elseans=99999;
int abss(int a){
	if(a<0){
		return -a;
	}
	return a;
}
void dfsset(int xx,int yy,int num){//dfsset函数设定斑点编号
	for(int i=0;i<4;i++){
		xx+=dx[i];
		yy+=dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&x[xx][yy]!='.'&&!vis[xx][yy]){
			vis[xx][yy]=1;
			a[xx][yy]=num;
			dfsset(xx,yy,num);
		}
		xx-=dx[i];
		yy-=dy[i];
	}
}
int trypoint(int i,int j){//第二种操作
	int xx[4];
	xx[1]=xx[2]=xx[3]=999999;
	for(int p=1;p<=n;p++){
		for(int q=1;q<=m;q++){
			if(x[p][q]=='X'){
				xx[a[p][q]]=min(xx[a[p][q]],abss(i-p)+abss(j-q)-1);
			}
		}
	}	
	return xx[1]+xx[2]+xx[3]+1;
}
int main(){
//	freopen("pageant.in","r",stdin);
//	freopen("pageant.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	for(int i=1;i<=n;i++){//读入
		for(int j=1;j<=m;j++){
			if(j==m&&i!=n){
				scanf("%1c\n",&x[i][j]);
			}else{
				scanf("%1c",&x[i][j]);
			}
		}
	}
	int num=0;
	for(int i=1;i<=n;i++){//设定斑点编号
		for(int j=1;j<=m;j++){
			if(x[i][j]=='.'){
				continue;
			}
			if(vis[i][j]==0){
				num++;
				a[i][j]=num;
				dfsset(i,j,num);
			}
		}
	}
	
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++){//循环查找
		for(int j=1;j<=m;j++){
			if(x[i][j]=='X'){
				for(int k=1;k<=n;k++){//第一种操作
					for(int l=1;l<=m;l++){
						if(a[k][l]==0){
							continue;
						}
						if(a[k][l]!=a[i][j]&&dis[a[i][j]][a[k][l]]>abss(i-k)+abss(j-l)){
							dis[a[k][l]][a[i][j]]=min(dis[a[k][l]][a[i][j]],abss(i-k)+abss(j-l));
						}
					}
				}
			}else{
				elseans=min(elseans,trypoint(i,j));//第二种操作
			}
		}
	}
	int anss=elseans;
	for(int i=1;i<=3;i++){//值得一提的是，这里要把dis[1][2]和dis[2][1]合并一下，不然7个点会变红哦
		for(int j=i+1;j<=3;j++){
			if(dis[i][j]!=0){
				dis[i][j]=min(dis[j][i],dis[i][j]);
			}
		}
	}
	anss=min(anss,min(dis[1][2]+dis[2][3]-2,min(dis[1][2]+dis[1][3]-2,dis[1][3]+dis[2][3]-2)));
	printf("%d",anss);
	return 0;
}

写题解不易，点赞再走吧