挑战程序设计竞赛--迷宫问题(BFS)

挑战程序设计竞赛第二个程序,迷宫的最短路径问题,因为没有找到平台测试的,所以简单写了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版权协议,转载请附上原文出处链接和本声明。