题目
题目描述
输入输出格式
输入输出样例
输入样例#1：
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....
输出样例#1：
4
题解
$bfs$+$dfs$
枚举$4$个方向，$bfs$将每个点染色，形成三块颜色块
$dfs$处理每个颜色块到其他点的最短距离，注意是点
最后非常暴力的枚举每一个点到其他颜色块的距离
处理处每个颜色块的最小距离，找出两个最小的加起来
注意$ans$最后要$-2$，因为$dfs$处理时点和涂色点有重合
我前几次处理颜色块都是处理的点竟然还得了$66$分……
代码
# include<iostream>
# include<cstdio>
# include<queue>
# include<cstdlib>
# include<cstring>
#define inv inline void
#define ini inline int
using namespace std;
struct p{
int x,y;
};
int n,m,cut;
char a[51][51];
int mv1[4]={0,0,1,-1};
int mv2[4]={1,-1,0,0};
int col[51][51];
int d[4][51][51],minn[4][4];
inv bfs(int x,int y)
{
cut++;
col[x][y]=cut;
queue<p>qu;
qu.push((p){x,y});
while(!qu.empty())
{
p t=qu.front();
qu.pop();
for(int i=0;i<4;i++)
{
int xx=t.x+mv1[i],yy=t.y+mv2[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!col[xx][yy]&&a[xx][yy]=='X')
{
col[xx][yy]=cut;
qu.push((p){xx,yy});
}
}
}
}
inv dfs(int cl,int x,int y,int tot)
{
if(tot>=d[cl][x][y]) return;
d[cl][x][y]=tot;
for(int i=0;i<4;i++)
{
int xx=x+mv1[i],yy=y+mv2[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
dfs(cl,xx,yy,tot+1);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!col[i][j]&&a[i][j]=='X')
bfs(i,j);
memset(d,127/3,sizeof(d));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='X')
dfs(col[i][j],i,j,0);
memset(minn,127/3,sizeof(minn));
int ans=999999;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='X')
{
minn[col[i][j]][1]=min(minn[col[i][j]][1],d[1][i][j]);
minn[col[i][j]][2]=min(minn[col[i][j]][2],d[2][i][j]);
minn[col[i][j]][3]=min(minn[col[i][j]][3],d[3][i][j]);
minn[1][col[i][j]]=minn[col[i][j]][1];
minn[2][col[i][j]]=minn[col[i][j]][2];
minn[3][col[i][j]]=minn[col[i][j]][3];
}
ans=min(minn[1][2]+minn[2][3],min(minn[1][3]+minn[1][2],minn[2][3]+minn[1][3]));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=min(ans,d[1][i][j]+d[2][i][j]+d[3][i][j]);
ans-=2;
printf("%d",ans);
return 0;
}
