走迷宫

　

走迷宫

这里面的由递归打印路径到非递归实现路径打印，十分好

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include <iOStream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=105;
#define ll long long
int n,m,xs,ys,xt,yt;
//maze放图
int maze[maxn][maxn],vis[maxn][maxn],fa[maxn][maxn];
int dist[maxn][maxn],last_dir[maxn][maxn],num[maxn][maxn];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
char name[]="UDLR";
int q[maxn*maxn];
void bfs(int x,int y)
{
    int front=0,rear=0,d,u;
    u=x*m+y;
    vis[x][y]=1;
    fa[x][y]=u;
    dist[x][y]=0;
    q[rear++]=u;
    while(front<rear)
    {
        u=q[front++];
        x=u/m;y=u%m;
        for(d=0;d<4;d++)
        {
            int nx=x+dx[d],ny=y+dy[d];
            //maze为1时表示空地
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]&&!vis[nx][ny])
            {
                int v=nx*m+ny;
                q[rear++]=v;
                vis[nx][ny]=1;
                fa[nx][ny]=u;
                dist[nx][ny]=dist[x][y]+1;
                last_dir[nx][ny]=d;

            }
        }
    }
}
void print_path(int x,int y)
{
    int fx=fa[x][y]/m;
    int fy=fa[x][y]%m;
    if(fx!=x||fy!=y)
    {
        //用递归从起点开始打印
        print_path(fx,fy);
        putchar(name[last_dir[x][y]]);
    }
}
//由print_path的递归到print_path2的非递归的优化是值得学习的地方
int dir[maxn*maxn];
void print_path2(int x,int y)
{
    int c=0;
    for(;;)
    {
        int fx=fa[x][y]/m;
        int fy=fa[x][y]%m;
        if(fx==x&&fy==y) break;
        dir[c++]=last_dir[x][y];
        x=fx;
        y=fy;
    }
    while(c--)
    {
        putchar(name[dir[c]]);
    }
}
int main()
{
    int i,j;
    scanf("%d%d%d%d%d%d",&n,&m,&xs,&ys,&xt,&yt);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&maze[i][j]);
    memset(vis,0,sizeof(vis));
    bfs(xs,ys);
    print_path(xt,yt);
    putchar('\n');
    print_path2(xt,yt);
    putchar('\n');
    return 0;
}

相关阅读

想要的资源百度搜不到？6个只有老师傅才知道的网站，悄悄

  总有些想要的资源，百度翻了几十页都找不到。怎么办呢？不妨试试下面这6个资源搜索网站，想要的资源几秒就能找到，让你大饱眼福。 BT

从线上到线下，UGC正在如何进化？走向哪？

最近灵泛工作室与百度展开合作，在百度直达号上开辟了“@十万喵星人计划”，用户可以直接进入该页面创作喵星人，与传统线上不同的是4月

荷尔蒙经济爆发，情趣平台怎么走？

【导读】对于90后出身的马佳佳、刘克楠而言，他们正好处在一个非常微妙的时机，旧的秩序正在崩溃，新的秩序还未建立，而90后正好带着某种

马走日

马走日总时间限制: 1000ms 内存限制: 1024kB描述马在中国象棋以日字形规则移动。请编写一段程序，给定n*m大小的棋盘，以及马的初始位

如何在手机上查询淘宝商品的历史价格走势?

我们购物经常去淘宝或天猫买东西，但是电商的商品价格会随着季节和活动经常有变化，双十一往往是价格最低的，有时不同的商家也会不定期