BFS
求最短路:边权都相同时才可以用BFS
思路
1.用队列存储第一个元素
2.然后队头向四周扩展找到符合条件的元素入队(rear)
3.队头出队(front )
4.循环2和3步骤
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int f[N][N];//存储图
int d[N][N];//存储离起点的距离
typedef pair<int,int>PII;
int front,rear=-1;
PII q[N*N];//队列 应该为N*N,因为存储的是图里面的点
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};//方向数组
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&f[i][j]);
}
memset(d,-1,sizeof(d));//长度初始化为-1
q[++rear]={1,1};
d[1][1]=0;//起始点位置为0
while(rear>=front)
{
for(int i=0;i<4;i++)//向四周扩展
{
int x=q[front].first+dx[i];
int y=q[front].second+dy[i];
if(x>=1&&y>=1&&x<=n&&y<=m&&f[x][y]==0&&d[x][y]==-1)(1)要加d[x][y判断是否已经走过,否则要发生段错误
{
q[++rear].first=x;
q[rear].second=y;
d[x][y]=d[q[front].first][q[front].second]+1;
}
}
front++;
}
cout<<d[n][m];
return 0;
}
扩展:记录路径
加一个数组,在由某个点(A)扩展开的点(B)入队时,将A记录在B的mmin数组中,这样可以通过mmin数组找到B的前一个点,由此可记录下最短路径
#include<bits/stdc++.h>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
int f[N][N];
int n,m;
int dt[N][N];//共有n*m个点
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};
bool used[N][N];
PII q[N*N];
int front,rear=-1;
PII mmin[N][N];//记录最短路径
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&f[i][j]);
}
used[1][1]=true;
q[++rear]={1,1};
dt[1][1]=0;
mmin[1][1]={-1,-1};
while(rear>=front)
{
auto t=q[front++];
int x=t.first,y=t.second;
for(int i=0;i<4;i++)
{
int vx=x+dx[i];
int vy=y+dy[i];
if(!used[vx][vy]&&vx>=1&&vx<=n&&vy>=1&&vy<=m&&!f[vx][vy])
{
q[++rear]={vx,vy};
used[vx][vy]=true;
dt[vx][vy]=dt[x][y]+1;
mmin[vx][vy]=t;
}
}
}
printf("%d",dt[n][m]);
puts("");
auto t=mmin[n][m];
while(t.first>=0)
{
cout<<t.first<<" "<<t.second<<endl;
t=mmin[t.first][t.second];
}
return 0;
}