算法一:bfs
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define f first
#define s second
typedef pair<int,int> PII;
const int N=51;
int n,m,st[N][N],cnt,re=1e9;
char g[N][N];
vector<PII> ps[2];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void bfs(int x,int y,int cnt)
{
queue<PII> q;
q.push({x,y});
st[x][y]=1;
while(!q.empty())
{
PII t=q.front();
q.pop();
ps[cnt].push_back(t);
for(int i=0;i<4;i++)
{
int X=t.f+dx[i],Y=t.s+dy[i];
if(X<0||X>=n||Y<0||Y>=m||st[X][Y]||g[X][Y]!='X')
continue;
st[X][Y]=1;
q.push({X,Y});
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>g[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!st[i][j]&&g[i][j]=='X')
bfs(i,j,cnt++);
}
}
for(auto& a:ps[0])
{
for(auto& b:ps[1])
{
re=min(re,abs(a.f-b.f)+abs(a.s-b.s)-1);
}
}
cout<<re;
return 0;
}
算法二:dfs
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=51;
#define f first
#define s second
typedef pair<int,int> PII;
int n,m,st[N][N],cnt,re=1e9;
char g[N][N];
vector<PII> ps[2];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void dfs(int a,int b,int cnt)
{
ps[cnt].push_back({a,b});
st[a][b]=1;
for(int i=0;i<4;i++)
{
int x=a+dx[i],y=b+dy[i];
if(x<0||y<0||x>=n||y>=m||st[x][y]||g[x][y]!='X')
continue;
dfs(x,y,cnt);
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>g[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!st[i][j]&&g[i][j]=='X')
dfs(i,j,cnt++);
}
}
for(auto& a:ps[0])
{
int x1=a.f,y1=a.s;
for(auto& b:ps[1])
{
int x2=b.f,y2=b.s;
re=min(re,abs(x1-x2)+abs(y1-y2)-1);
}
}
cout<<re;
return 0;
}