题解 P6131 【[USACO11NOV]Cow Beauty Pageant S】

qzhwlzy · 2020-11-05 16:08:12 · 题解

传送#1

传送#2

思路

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

读入，将三个斑点依次编号为1,2,3，方法有很多，如 dfs 或 bfs ，这里不细讲了。
关键步骤，我们知道，对于任意两个斑点，无非只有上图所示的两种情况，因此，我们需要分别计算两种情况改变的最小格子数（以下称为距离）。
- 第一种，将两个斑点连通至第三个斑点，需要我们分别记录每两个斑点之间的距离，一共就三种情况。
- 第二种，将三个斑点连至一个不在斑点上的点，我们就可以循环每一个不在斑点上的点，计算距离并求最小值。

计算过程

依次循环每一个点，如果是‘ 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;
}