解题思路:从原点向右左上下遍历,遍历时要检查是否符合要求
要求不是路障#,且没有遍历过visited[x][y]==0
注意事项:注意移动的方法d[4][2]
参考代码:
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int r,c;
char mp[N][N];
int visited[N][N];
typedef struct node
{
int x,y;
int step;//统计多少步
}Node;
int d[4][2]={ {0,1},
{0,-1},
{1,0},
{-1,0}
};//后续用于移动
int check(Node p)//检查是否可以通行
{
if(p.x<0 || p.x>=r || p.y<0 || p.y>=c) return 0;
if(mp[p.x][p.y]=='#') return 0;
return 1;//否则可以通行.
}
int bfs(Node begin,Node end)
{
queue<Node> q;//初始化队列
q.push(begin);
visited[begin.x][begin.y]=1;
while(!q.empty())//非空
{
Node top=q.front();//取队首
q.pop();//出队,让移动后的符合要求(.)的位置成为新的队首
if(top.x==end.x && top.y==end.y)
return top.step+1;
//以题所定,题目求得是一共进过的点的个数(包括第一个和最后一个
for(int i=0;i<4;i++)//使四个方向都尝试移动过
{
Node newnode;
newnode.x=top.x+d[i][0];//移动
newnode.y=top.y+d[i][1];//移动
if(check(newnode)==1 && visited[newnode.x][newnode.y]==0)
//可以通行,且没有通行过
{
newnode.step=top.step+1;
q.push(newnode);
visited[newnode.x][newnode.y]=1;
}
}
}
return -1;
}
int main()
{
cin>>r>>c;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
cin>>mp[i][j];
Node begin,end;
begin.x=0;begin.y=0;begin.step=0;
end.x=r-1;end.y=c-1;
int cnt=bfs(begin,end);
cout<<cnt<<endl;
return 0;
}
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复