思路:
- 将两块斑点分别放进两个数组
- 遍历两个数组中的每个点的距离,取最小值
我们先用广搜分块
void bfs(int sx,int sy){
cnt++;
v[sx][sy]=true;
q.push({sx,sy});
pt[cnt].push_back({sx,sy});
while(!q.empty()){
PII top=q.front();
q.pop();
int tx=top.first,ty=top.second;
for(int i=0;i<4;i++){
int x=tx+dx[i],y=ty+dy[i];
if(x<1 || y<1 || x>n || y>m || a[x][y]=='.' || v[x][y]) continue;
q.push({x,y});
v[x][y]=true;
pt[cnt].push_back({x,y});
}
}
}
下面是主函数的输入处理及遍历求答案
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(a[i][j]=='X'&& v[i][j]==false) bfs(i,j);
}
}
for(int i=0;i<pt[1].size();i++){
for(int j=0;j<pt[2].size();j++){
PII c=pt[1][i],d=pt[2][j];
int b=abs(c.first-d.first)+abs(c.second-d.second)-1;
mi=min(mi,b);
}
}
cout<<mi;
return 0;
}