算法2 两个bfs
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll n,m,k;
const int N = 110;
char s[N][N];
int dist[N][N];
int dx[] = {0,1,-1,0},dy[] = {1,0,0,-1};
bool st[N][N];
vector<PII> bfs(int x1,int y1)
{
vector<PII> v;
queue<PII> p;
p.push({x1,y1});
st[x1][y1] = true;
while(p.size())
{
PII t = p.front();
p.pop();
v.push_back({t.first,t.second});
for(int i = 0;i<4;i++)
{
int x = t.first + dx[i],y = t.second + dy[i];
if(x<1||x>n||y<1||y>m||s[x][y]!='X'||st[x][y]) continue;
st[x][y] = true;
p.push({x,y});
}
}
return v;
}
int main()
{
memset(dist,0x3f,sizeof dist);
cin >> n >> m;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
cin >> s[i][j];
}
}
vector<PII> a,b;
bool flag = false;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
if(s[i][j] == 'X' && !st[i][j])
{
if(!flag)
{
a = bfs(i,j);
flag = true;
}
else b = bfs(i,j);
}
}
}
queue<PII> p;
for(int i = 0;i<a.size();i++)
{
dist[a[i].first][a[i].second] = 0;
p.push({a[i].first,a[i].second});
}
while(p.size())
{
PII t = p.front();
p.pop();
for(int i = 0;i<4;i++)
{
int x = t.first + dx[i],y = t.second + dy[i];
if(x<1||x>n||y<1||y>m) continue;
if(dist[x][y] > dist[t.first][t.second] + 1)
{
dist[x][y] = dist[t.first][t.second] + 1;
p.push({x,y});
}
}
}
int ans = 1e9;
for(int j = 0;j<b.size();j++)
{
ans = min(ans,dist[b[j].first][b[j].second]);
}
cout<< ans - 1<<endl;
return 0;
}