题目描述
dfs+多源bfs
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
char g[55][55];
int n,m;
int ans=INF;
bool st[55][55];//区别两个斑点
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
queue<PII> q;
int dist[55][55];//dist[i][j]表示由(i,j)到另一个块的最短距离
void dfs1(int x,int y)
{
st[x][y]=true;
q.push({x,y});
dist[x][y]=0;
for(int i=0;i<4;i++)
{
int x0=x+dx[i];
int y0=y+dy[i];
if(x0<=0||y0<=0||x0>n||y0>m||g[x0][y0]=='.'||st[x0][y0]) continue;
dfs1(x0,y0);
}
}
void bfs()
{
while(q.size())
{
auto t=q.front();
q.pop();
int x=t.first,y=t.second;
if(g[x][y]=='X'&&!st[x][y])//找到了另一块斑点中的X
{
ans=min(ans,dist[x][y]);
}
for(int i=0;i<4;i++)
{
int x0=x+dx[i];
int y0=y+dy[i];
if(x0<=0||y0<=0||x0>n||y0>m||dist[x0][y0]!=-1) continue;
dist[x0][y0]=dist[x][y]+1;
q.push({x0,y0});
}
}
}
int main()
{
cin>>n>>m;
int x0,y0;
bool flag=true;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
if(flag&&g[i][j]=='X')//确定其中一个块内的一个X,用于后面的dfs操作,将两个块中的X区分开
{
flag=false;
x0=i,y0=j;
}
}
}
memset(dist,-1,sizeof dist);//初始化距离,多源bfs的必要操作
dfs1(x0,y0);
bfs();
cout<<ans-1;//答案是求点数,为最短路径-1
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla