洛谷P2124 奶牛美容

https://www.luogu.com.cn/problem/P2124

我以为是个很水的bfs

果然人家有坑点

有可能是以一个“.”为桥梁，连接了三个"X"

所以还需要求出3个“X”组到每个“.”的最短距离

选出那一个桥

例：

X.X

.X.

#include<cstdio>
#include<algorithm> 

using namespace std;

#define N 51

int n,m;
char mp[N][N]; 
bool vis[N][N];
int id[N][N],cnt;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int f[4][N][N],g[4][4];

void dfs(int x,int y,int bl)
{
    id[x][y]=bl;
    vis[x][y]=true;
    int nx,ny;
    for(int i=0;i<4;++i)
    {
        nx=x+dx[i];
        ny=y+dy[i];
        if(nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny] || mp[nx][ny]!='X') continue;
        dfs(nx,ny,bl);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%s",mp[i]+1);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(mp[i][j]=='X' && !vis[i][j])  
                dfs(i,j,++cnt);
    for(int k=1;k<=3;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                f[k][i][j]=1e9;
    for(int i=1;i<=3;++i)
        for(int j=1;j<=3;++j)
            g[i][j]=1e9;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(mp[i][j]=='X')
                for(int k=1;k<=n;++k)
                    for(int l=1;l<=m;++l)
                    {
                        f[id[i][j]][k][l]=min(f[id[i][j]][k][l],abs(k-i)+abs(l-j)-1);
                        if(mp[k][l]=='X' && id[i][j]!=id[k][l])
                            g[id[i][j]][id[k][l]]=min(g[id[i][j]][id[k][l]],abs(k-i)+abs(l-j)-1);
                    }
    int ans=min(min(g[1][2]+g[2][3],g[1][2]+g[1][3]),g[1][3]+g[2][3]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(mp[i][j]!='X')
                ans=min(ans,f[1][i][j]+f[2][i][j]+f[3][i][j]+1);
    printf("%d",ans);
}