题目描述
blablabla
样例
/*
注意两个点的距离怎么求 这里是只有上下左右 两个点的距离满足曼哈顿距离
所以我们可以通过广搜把两个X的大区间内的点分别存入到两个数组 然后枚举更新最小值
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int MAX = 1e5+7;
typedef pair<int,int>pai;
vector<pai>a,b;
int vis[55][55];
char path[55][55];
int flag = 0;
int n,m;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
void bfs(int x,int y)
{
queue<pai>q;
if(flag == 0)
a.push_back({x,y});
else
b.push_back({x,y});
q.push({x,y});
while(!q.empty())
{
pai t = q.front();
q.pop();
int ax = t.first;
int ay = t.second;
for(int i=0;i<4;i++){
int xx = ax+dx[i];
int yy = ay+dy[i];
if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&path[xx][yy]=='X'&&vis[xx][yy]==0){
vis[xx][yy]=1;
if(flag == 0)
a.push_back({xx,yy});
else
b.push_back({xx,yy});
q.push({xx,yy});
}
}
}
}
void solve()
/*算数开ll 存图用int*/
{
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>path[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(path[i][j] == 'X' && vis[i][j] == 0){
vis[i][j] = 1;
bfs(i,j);
flag = 1;
}
}
}
int ans = INF;
for(int i=0;i<a.size();i++){
for(int j=0;j<b.size();j++){
ans=min(ans,abs(a[i].first-b[j].first)+abs(a[i].second-b[j].second));
}
}
cout<<ans-1;
}/*算数开ll 存图用int*/
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
cout.tie(0);
//cout<<fixed<<setprecision(2);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla