模拟队列
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;
const int N = 110;
typedef pair<int,int> PII;
int d[N][N];//记录当前点到起点的距离
PII q[N*N];
int g[N][N];
int n,m;
int bfs()
{
int hh=0,tt=0;
q[0] = {0,0};
memset(d ,-1 ,sizeof d);
d[0][0] = 0;
while(hh<=tt)
{
auto t = q[hh++]; //取出队头元素,并出队
int dx[4] = {-1,0,1,0},dy[4]={0,-1,0,1};
for(int i=0;i<4;i++)
{
int x = t.first + dx[i], y = t.second+dy[i]; //x,y表示坐标
if(x>=0 && y>=0 && x<n && y<m && d[x][y]==-1 && g[x][y]==0)
{
d[x][y] = d[t.first][t.second]+1;
q[++tt] = {x,y};
}
}
}
return d[n-1][m-1];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
cout<<bfs();
}
使用STL
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 110;
int g[N][N];
int d[N][N];
queue<PII> q;
int n,m;
int bfs()
{
q.push({0,0});
memset(d,-1,sizeof d);
d[0][0] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
int dx[4] = {-1,0,1,0} , dy[4] = {0,1,0,-1};
for(int i=0;i<4;i++)
{
int x = t.first+dx[i] , y = t.second+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&d[x][y] == -1&&g[x][y] ==0)
{
d[x][y] = d[t.first][t.second] + 1;
q.push({x,y});
}
}
}
return d[n-1][m-1];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
cout<<bfs();
return 0;
}
总结
- bfs模板感觉就是使用队列,做这种最小步数,最短路径,无非就是从起点开始枚举四个方向,而这四个方向可以用向量来表示 dx[4] = {1,0,-1,0} , dy[4] = {0,-1,0,1}只要能对应上下左右四个方向即可
- 存储问题,例如八数码,使用字符串来存取,然后将一维数组下标转换为二维数组,既x = 数据个数/行 , y = 数据个数%列;
- bfs直接一层一层枚举,而dfs则是一条边一条边枚举