C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 468K, 提交时间: 2020-10-19 21:08:04

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
int n,m,ans=520520520,p[55][55],cnt,f[55][55],tot,dis[4][55][55];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
char s[55][55];
bool vis[55][55],lian[4];
il void change(int x,int y,int c){
    if(vis[x][y])return ;
    if(s[x][y]=='X'){vis[x][y]=1;p[x][y]=c;}
    else return;
    for(int i=0;i<4;i++){
        int xx=dx[i]+x,yy=dy[i]+y;
        change(xx,yy,c);
    }
}
il void dfs(int kuai,int x,int y){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dis[kuai][i][j]=min(dis[kuai][i][j],abs(i-x)+abs(j-y));
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if(s[i][j]=='X'&&!vis[i][j])change(i,j,++cnt);
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if(s[i][j]=='X')dfs(p[i][j],i,j);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if(s[i][j]=='X'){
            f[p[i][j]][1]=min(f[p[i][j]][1],dis[1][i][j]);
            f[p[i][j]][2]=min(f[p[i][j]][2],dis[2][i][j]);
            f[p[i][j]][3]=min(f[p[i][j]][3],dis[3][i][j]);
            f[1][p[i][j]]=f[p[i][j]][1];
            f[2][p[i][j]]=f[p[i][j]][2];
            f[3][p[i][j]]=f[p[i][j]][3];
    }
    ans=min(f[1][2]+f[2][3],min(f[1][3]+f[1][2],f[1][3]+f[2][3]));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=min(ans,dis[1][i][j]+dis[2][i][j]+dis[3][i][j]);
    cout<<ans-2;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 71ms, 内存消耗: 456K, 提交时间: 2020-10-19 11:41:20

#include<bits/stdc++.h>
using namespace std;
int ma[105][105];
int f[105][105];
int n,m,tot,ans;
char t;
int kx[6]={0,1,-1,0,0};
int ky[6]={0,0,0,1,-1};
void dfs(int x,int y)
{
	ma[x][y]=tot;
	for(int i=1;i<=4;i++){
		int tx=x+kx[i];
		int ty=y+ky[i];
		if(tx>0&&ty>0&&tx<=n&&ty<=m&&ma[tx][ty]==0)
			dfs(tx,ty);
	}
}
struct oppo{
	int x,y,s;
}st;
queue<oppo> v;
bool vis[105][105];
int dis[10];
int bfs(int xx,int yy,int fa)
{
	memset(vis,0,sizeof(vis));
	vis[xx][yy]=1;
	st.x=xx;st.y=yy;st.s=0;
	v.push(st);
	while(v.size()){
		oppo lxl=v.front();
		if(ma[lxl.x][lxl.y]==fa){
			while(v.size()) v.pop();
			return lxl.s;
		}
		v.pop();
		for(int i=1;i<=4;i++){
			int tx=lxl.x+kx[i];
			int ty=lxl.y+ky[i];
			if(tx>0&&ty>0&&tx<=n&&ty<=m&&vis[tx][ty]==0){
				vis[tx][ty]=1;
				st.x=tx;st.y=ty;st.s=lxl.s+1;
				v.push(st);
			}
		}
	}
	return -1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>t;
			ma[i][j]= t=='X'?0:-1;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(ma[i][j]==0){
				tot++;
				dfs(i,j);
			}
	ans=dis[1]=dis[2]=dis[3]=1500;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(ma[i][j]>0){
				for(int k=ma[i][j]+1;k<=3;k++)
					dis[ma[i][j]+k-2]=min(dis[ma[i][j]+k-2],bfs(i,j,k));
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(ma[i][j]==-1)
				ans=min(ans,bfs(i,j,1)+bfs(i,j,2)+bfs(i,j,3)-2);
	sort(dis+1,dis+4);
	cout<<min(ans,dis[1]+dis[2]-2)<<"\n";
	return 0;
}