//BFS版 //理解：因为BFS是一层一层的展开的，所以需要一个队列来存储这一层所有的点，从而进行一个点一个点的拓展，等找到我们需要的点时，便可以终止BFS #include using namespace std; const int N=105; int Map[N][N]; //记录迷宫 int flag[N][N]; //记录点有没有被走过，并且记录当前点走了有多少步 pair Start,End,Now,Next; //now和next代表当前这个点（坐标）和下一个点（移动后的点） queue> loc; int n,m,res=0; //res最后会减1，如果找不到正确路径，减了1后就会变为-1，符合题意 //分别代表上下左右 int zou1[]={0,0,-1,1}; int zou2[]={1,-1,0,0}; bool pd(int x,int y) //pd函数用来判断是否越界 { if(x<1)return false; else if(x>n)return false; else if(y<1)return false; else if(y>m)return false; else if(Map[x][y]!=1)return false; //地图上不能走的点 else if(flag[x][y]!=0)return false; //flag[x][y]!=0说明已经走过这个点了 else return true; } bool check(int x,int y) //check函数用来判断是否已经到达了终点 { if(x==End.first&&y==End.second) { res=flag[x][y]; //让结果等于终点那个点所统计出来的距离 return true; } else return false; } void bfs() { while(!loc.empty()) { Now=loc.front(); loc.pop(); if(check(Now.first,Now.second)) { //如果check函数对于当前的坐标发现其是终点，则会让bfs直接停止 return ; } else //如果当前点不是终点，则继续搜索 { for(int i=0;i<4;i++) { Next.first=Now.first+zou1[i]; Next.second=Now.second+zou2[i]; if(pd(Next.first,Next.second)) //用pd函数判断一下这个拓展的点有没有越界 //注意：因为起点一定不是终点，所以一开始并不需要用pd函数判断是否越界，所以直接判断下一个点，而这下一个点也正是下一次循环的“起点”，所以pd函数才会放在这个用for循环拓展新的点的这里 { loc.push(Next); flag[Next.first][Next.second]=flag[Now.first][Now.second]+1; } } } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>Map[i][j]; } } cin>>Start.first>>Start.second>>End.first>>End.second; loc.push({Start.first,Start.second}); flag[Start.first][Start.second]=1; //开始的点距离为1，最后结果会减去这个1 bfs(); cout<

“15 届蓝桥杯 14 天省赛冲刺营 1 期”实验报告