题目描述
题目思路,先把两个斑点用dfs搜索出来存进去,然后寻找两个斑点中点的最短距离(此题范围小,用暴力即可)
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=55;
int n,m;
char g[N][N];
vector<PII> points[2];//用来存放两个斑点
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//俗称dfs搜索四条爪,顺序:上右下左
void def(int a,int b,vector<PII>& q){
q.push_back({a,b});//将斑点块中的点坐标存起来
g[a][b]='.';//存完之后,更改,防止再次存入,因为下个点的前后左右还会所搜到这个点
for(int j=0;j<4;j++){//遍历这个点的前后左右
int x=a+dx[j],y=b+dy[j];
if(x>=0 && x<n && y>=0 && y<m && g[x][y]=='X'){//如果合适,则遍历下个点的前后左右
def(x,y,q);
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) cin>>g[i][j];
}
int k=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='X'){
def(i,j,points[k++]);//两个points用来存放俩斑点块
}
}
}
int res=110;
//暴力搜索即可
for(auto &a: points[0]){
for(auto &b: points[1]){
res=min(res,abs(a.x-b.x)+abs(a.y-b.y));
}
}
cout<<res-1;
return 0;
}