解题思路:
bfs刚好满足于queue的逻辑,
运用queue对每次新的坐标入队
具体代码如下
参考代码:
#include<iostream> #include<queue> using namespace std; const int MAXC = 1000; int r,c; char mapp[MAXC][MAXC]; int vis[MAXC][MAXC]; int start_x,start_y; int end_x,end_y; int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; void bfs(){ //这是一个队列(queue)的定义,其中每个元素是一个pair类型,pair中包含两个int类型的元素。 queue<pair<int , int >> q; //其中q是一个queue类型的变量,make_pair(start_x, start_y)是一个pair类型的变量, //表示一个二元组,将start_x和start_y打包在一起。这行代码的作用是将这个二元组压入队列q中。 q.push(make_pair(start_x,start_y)); vis[start_x][start_y] = 1; //因为考虑到“计算步数要包括起点和终点。”所以step初始值给1表示起点步数 int step = 1; while(!q.empty()){ int len = q.size(); while(len--){ int x = q.front().first; //取出的第一个数值被赋值给变量x int y = q.front().second; //第二个数值被赋值给变量y //这段代码是从队列(queue)中取出第一个元素,并将其弹出队列。 q.pop(); if(x == end_x && y == end_y){ //判断该坐标(x,y)是否到达终点(end_x,end_y) cout<<step; return; } for(int i=0;i<4;i++){ //将坐标(x,y)向四个方向分别偏移一定量,得到四个新的坐标(dx,dy)。 int dx = x + d[i][0]; int dy = y + d[i][1]; if(dx>0 && dx<=r && dy>0 && dy<=c && !vis[dx][dy] && mapp[dx][dy]=='.' ){ //枚举4个方向,合适的就入队 q.push(make_pair(dx,dy)); vis[dx][dy] = 1; } } } step++; } cout<<"not answer"; //没答案输出-1。因题目所给案例都可以走出迷宫,所以可以计较 } int main(void){ cin>>r>>c; for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ cin>>mapp[i][j]; } } start_x = 1;start_y = 1; //对起点进行标记,坐标赋值给start_x,start_y; end_x = r; end_y = c; //对终点坐标进行标记 bfs(); return 0; }
0.0分
2 人评分
数字整除 (C++代码)——(22行代码)真的只需要两个变量就够了浏览:1808 |
第一浏览:871 |
C二级辅导-分段函数 (C语言代码)浏览:868 |
C语言程序设计教程(第三版)课后习题8.9 (C++代码)浏览:853 |
母牛的故事 (C语言代码)浏览:1716 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:529 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:661 |
C语言训练-大、小写问题 (C语言代码)浏览:614 |
A+B for Input-Output Practice (C语言代码)浏览:468 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:616 |