迷宫最短路径问题-BFS

C++实现：

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;

const int INF=100;
typedef struct node{
int x;
int y;
int dr; //从上一结点到这个结点的方向
struct node *last;
}*NODE;
NODE sp=NULL; //开始点
NODE gp=NULL; //结束点
int N=10,M=10;
int sx,sy;
int gx,gy;
char maze[10][11]={"#.######.#",
"......#..#",
".#.##.##.#",
".#........",
"##.##.####",
"....#....#",
".#######.#",
"....#.....",
".####.###.",
"....#....#"};
int d[10][10];

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int bfs()
{
queue<NODE> que;
    sp = (struct node*)malloc(sizeof(struct node));
for(int i=0;i<N;i++)
for(int j=0;j<M;j++) d[i][j]=INF;
    sp->x=sx;sp->y=sy;
    sp->dr=0;sp->last=sp;
    que.push(sp);
    d[sx][sy]=0;
while(!que.empty()){
        NODE p1 = que.front();que.pop();
if(p1->x==gx && p1->y==gy){
            gp=p1;
break;
        }

for(int i=0;i<4;i++){
int nx=p1->x+dx[i],ny=p1->y+dy[i];

if(nx>=0 && nx<N && ny>=0 && ny<M && maze[nx][ny]=='.'&& d[nx][ny]==INF){
                NODE p2 = (struct node*)malloc(sizeof(struct node));
                p2->x=nx;p2->y=ny;
                p2->last = p1;p2->dr=i;
                que.push(p2);
                d[nx][ny] = d[p1->x][p1->y]+1;
            }
        }
    }
return d[gx][gy];
}

void fuc1(int i,int j)
{
if( i==0 && j==0 ){
for(int t=0;t<=N+1;t++){
cout<<"■";
        }
cout<<endl;
    }
if(j==0) cout<<"■";
}

void fuc2(int i,int j)
{
if(j==M-1) cout<<"■";
if( i==N-1 && j==M-1 ){
cout<<endl;
for(int t=0;t<=N+1;t++){
cout<<"■";
        }
    }

}

int main()
{
for(int i=0;i<N;i++)
    {
for(int j=0;j<M;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
    }

    sx=0;sy=1;
    gx=N-1;gy=M-2;
int res = bfs();
string str[5] = {"↓","→","↑","←","■"};
char s[4] = {'0','1','2','3'};
if(res!=INF)
cout<<"最少需要"<<res<<"步到达终点"<<endl;
int t = gp->dr;
while(gp!=sp){
        gp=gp->last;
        maze[gp->x][gp->y]=s[t];
        t=gp->dr;
    }
for(int i=0;i<N;i++)
    {
for(int j=0;j<M;j++){
            fuc1(i,j); //加墙壁
if(i==sx && j==sy) cout<<"☆";
else if(i==gx && j==gy) cout<<"★";
else if(maze[i][j]=='#') cout<<str[4];
else if(maze[i][j]=='.') cout<<" ";
else{
switch(maze[i][j])
                {
case '0':cout<<str[0];break;
case '1':cout<<str[1];break;
case '2':cout<<str[2];break;
case '3':cout<<str[3];break;
default:cout<<maze[i][j];
                }
            }
            fuc2(i,j);
        }
cout<<endl;
    }
return 0;
}

输出样例：