挑战程序设计竞赛第二个程序,迷宫的最短路径问题,因为没有找到平台测试的,所以简单写了BFS的思路,变量命名的太糟糕啦!中间写的时候出现了好几次变量名冲突。
BFS的主要实现方式就是队列,所以整个程序重点就是写队列的循环,写的代码如下(变量名命名太糟糕啦)
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
char a[101][101];
int n,m;
typedef struct{
int i;
int j;
int num;
}node;
queue<node> p;
int main(){
int si,sj;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
if(a[i][j]=='S'){
si=i;
sj=j;
}
}
}
node s;
s.i=si;
s.j=sj;
s.num=0;
p.push(s);
int ans=0;
while(!p.empty()){
node n1=p.front();
p.pop();
if(n1.i-1>0&&a[n1.i-1][n1.j]=='.')
{
node q;
q.i=n1.i-1;
q.j=n1.j;
q.num=n1.num+1;
p.push(q);
}
if(n1.j-1>0&&a[n1.i][n1.j-1]=='.')
{
node q;
q.i=n1.i;
q.j=n1.j-1;
q.num=n1.num+1;
p.push(q);
}
if(n1.j+1<m&&a[n1.i][n1.j+1]=='.')
{
node q;
q.i=n1.i;
q.j=n1.j+1;
q.num=n1.num+1;
p.push(q);
}
if(n1.i+1<n&&a[n1.i+1][n1.j]=='.')
{
node q;
q.i=n1.i+1;
q.j=n1.j;
q.num=n1.num+1;
p.push(q);
}
if((n1.i-1>0&&a[n1.i-1][n1.j]=='G')||(n1.j-1>0&&a[n1.i][n1.j-1]=='G')||(n1.j+1<m&&a[n1.i][n1.j+1]=='G')||(n1.i+1<n&&a[n1.i+1][n1.j]=='G'))
{
ans=n1.num+1;
break;
}
}
if(ans==0)
printf("无解\n");
else
printf("%d\n",ans);
}
版权声明:本文为qq_43361691原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。