算法提高 学霸的迷宫 蓝桥杯

　　有100%的数据满足：1<=n,m<=500。

我原来运行错误的代码：

#include <cstring>#include <cstdio>#include <queue>#include<algorithm>using namespace std;#define max(a,b) ((a>b)?(a):(b))int n,m;char s[5]={'U','D','L','R'};int pos[510][510]={0};char revPRo[500];struct Node{int step;int x,y;char direct;Node*parent;Node*son[4];Node(){    parent=NULL;    for(int i=0;i<=3;i++)        son[i]=NULL;}};queue<Node*>q;Node*newNode(){return new Node();}void bfs(){Node*p,*d;int flag=0,k;while(1){    p=q.front();    for(int i=0;i<=3;i++){        switch(s[i]){        case 'U':if(p->x-1>=1&&pos[p->x-1][p->y]!=1){                 d=p->son[i]=newNode();                 d->parent=p;                 d->step=(p->step)+1;                 d->x=p->x-1;                 d->y=p->y;                 d->direct='U';                 q.push(p->son[i]);                }break;        case 'D':if(p->x+1<=n&&pos[p->x+1][p->y]!=1){                 d=p->son[i]=newNode();                 d->parent=p;                 d->step=(p->step)+1;                 d->x=p->x+1;                 d->y=p->y;                 d->direct='D';                 q.push(p->son[i]);                }break;        case 'L':if(p->y-1>=1&&pos[p->x][p->y-1]!=1){                 d=p->son[i]=newNode();                 d->parent=p;                 d->step=(p->step)+1;                 d->x=p->x;                 d->y=p->y-1;                 d->direct='L';                 q.push(p->son[i]);                }break;        case 'R':if(p->y+1<=m&&pos[p->x][p->y+1]!=1){                 d=p->son[i]=newNode();                 d->parent=p;                 d->step=(p->step)+1;                 d->x=p->x;                 d->y=p->y+1;                 d->direct='R';                 q.push(p->son[i]);                }break;}}        for(k=0;k<=3;k++){            if(p->son[k]==NULL)continue;            if(p->son[k]->x==n&&p->son[k]->y==m){                flag=1;                break;        }        }        if(flag)break;        q.pop();    }    printf("%d/n",p->son[k]->step);    int i=0;    p=p->son[k];    while(p->parent!=NULL){        revpro[i++]=p->direct;        p=p->parent;    }    i--;    while(i>=0){        printf("%c",revpro[i]);        i--;    }    printf("/n");}int main(){scanf("%d%d",&n,&m);getchar();memset(pos,0,sizeof(pos));memset(revpro,0,sizeof(revpro));for(int i=1;i<=n;i++){    for(int j=1;j<=m;j++){        pos[i][j]=getchar()-'0';    }    getchar();}Node*v;v=newNode();v->step=0;v->x=v->y=1;q.push(v);bfs();int y;scanf("%d",&y);return 0;}看到大神代码后改进的代码：
#include <cstring>#include <cstdio>#include <queue>#include<algorithm>using namespace std;#define max(a,b) ((a>b)?(a):(b))int n,m;char s[5]={'D','L','R','U'};//每次先遍历字典序小的节点的子节点int mov[4][2]={{1,0},{0,-1},{0,1},{-1,0}};//数组储存x,y变化，可以使用循环来加入下一个节点int pos[510][510]={0};//记录迷宫地形int vis[510][510]={0};//记录点是否被访问过的char revpro[10000];struct Node{int step;int x,y;char direct;Node*parent;Node*son[4];Node(){    parent=NULL;    for(int i=0;i<=3;i++)        son[i]=NULL;}};queue<Node*>q;Node*newNode(){return new Node();}int check(int tx,int ty){if(tx>n||tx<1)return 1;if(ty>m||ty<1)return 1;if(pos[tx][ty])return 1;return 0;}void bfs(){Node*p;int flag=0,i,tx,ty;while(1){    p=q.front();    q.pop();    for(i=0;i<=3;i++){        tx=p->x+mov[i][0];        ty=p->y+mov[i][1];        if(vis[tx][ty]||check(tx,ty))continue;//一个点不用被遍历两次，因为后面的点再遍历这点，要么路径不是字典序最 小，
                                                 要么步骤数多        p->son[i]=newNode();        p->son[i]->x=tx;        p->son[i]->y=ty;        vis[p->son[i]->x][p->son[i]->y]=1;        p->son[i]->parent=p;        p->son[i]->step=p->step+1;        p->son[i]->direct=s[i];        q.push(p->son[i]);        if(tx==n&&ty==m){            flag=1;            break;        }    }    if(flag)break;    }    printf("%d/n",p->son[i]->step);    int j=0;    p=p->son[i];    while(p->parent!=NULL){        revpro[j++]=p->direct;        p=p->parent;    }    j--;    while(j>=0){        printf("%c",revpro[j]);        j--;    }    printf("/n");}int main(){scanf("%d%d",&n,&m);getchar();for(int i=1;i<=n;i++){    for(int j=1;j<=m;j++){        pos[i][j]=getchar()-'0';    }    getchar();}Node*v;v=newNode();v->step=0;v->x=v->y=1;vis[1][1]=1;q.push(v);bfs();int y;scanf("%d",&y);return 0;}主要改进在于一个点不用遍历两次，大大减低了空间复杂度