题目描述
通过队列的作用实现了一层一层搜索
并用一个来储存距离一个来完成地图
重要的bfs函数在于的是 第一队列的生成 第二是队列部位空的时候 把队列的头取出并在满足条件下对
队列的头进行扩充
样例
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int ,int>PII;
const int N=110;
int g[N][N],f[N][N];
int n,m;
void bfs(int a,int b)
{
queue<PII>q;//第一步设立队列
q.push({a,b});//插入初始点
//两步操作完成我们对于队列的确定和初始值的设立
while(q.empty()!=1)
{
//第一步记录队首元素
PII start=q.front();
q.pop();//记录之后我们删除
g[start.first][start.second]=1;//将访问到的这个点标记为1记录已走
//下面从四个方向开始走
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
//向量组合的方法进行上下左右
for(int i=0;i<4;i++)
{
//再去确定可以走的点在哪里
int x=start.first+dx[i],y=start.second+dy[i];
if(g[x][y]==0)//没有被走过
{
g[x][y]=1;
f[x][y]=f[start.first][start.second]+1;
q.push({x,y});
}
}
} cout<<f[n][m];}
int main()
{
memset(g,1,sizeof(g));//由于在方阵内部我们进行访问所以我们需要对边界关注查看
cin>>n>>m;
for(int i=1;i<=n;i++)//初始的设立位置我们从1,1来展开
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
}
}
bfs(1,1);
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla