首先dfs:用flood fill的思想将两块分类,一块标记为1,类一块标记为2
然后bfs:一开始现将所有的标记1放入队列,然后返回第一个查找到2的步数-1即为答案
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 52;
int n,m;
int ans;
typedef pair<int, int> PII;
char ma[N][N];
int shu[N][N],use[N][N];
int idx=1;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
//标记分类
void dfs(int l,int r)
{
shu[l][r]=idx;
for(int i=0;i<4;i++)
{
int x=dx[i]+l,y=dy[i]+r;
if(x>=1&&x<=n&&y>=1&&y<=m&&shu[x][y]<1&&ma[x][y]=='X')
{
dfs(x,y);
}
}
}
//找最短步数
int bfs()
{
queue<PII>q;
memset(use,-1,sizeof use);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(shu[i][j]==1)
{
q.push({i,j});
use[i][j]=0;
}
}
}
while(q.size())
{
PII t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=dx[i]+t.first,y=dy[i]+t.second;
if(x>=1&&x<=n&&y>=1&&y<=m&&shu[x][y]!=1&&use[x][y]==-1)
{
use[x][y]=use[t.first][t.second]+1;
q.push({x,y});
if(shu[x][y]==2)
{
return use[x][y];
}
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ma[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ma[i][j]=='X'&&shu[i][j]==0)
{
dfs(i,j);
idx++;
}
}
}
cout<<bfs()-1;
}