文档章节

数据结构学习之队列破解迷宫

o
 osc_w9s1w4o0
发布于 2019/04/08 18:05
字数 727
阅读 3
收藏 0

精选30+云产品,助力企业轻松上云!>>>

数据结构学习之队列破解迷宫

0x1 问题描述

目的:掌握队列在求解迷宫问题中的应用。

内容:编写一个程序,求第一条最短路径长度及最短路径。

0x2 解答代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stack>
#define MaxSize 10000+7
#define M 8
#define N 8


using namespace std;
typedef int ElemType;
//typedef ElemType Box;
int mg[M+2][N+2]=
{
    {1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},
    {1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}
};
typedef struct
{
    int i,j; //position
    int pre; //前面指针
}Box; //type of block

int next[4][2] ={{-1,0},{0,1},{1,0},{0,-1}};
typedef struct
{
    Box data[MaxSize]; //domain of data
    int front,rear;
}QuType; //type of queue

//Init queue
void InitQueue(QuType *&q)
{
    q = (QuType *)malloc(sizeof(QuType));
    q->front=q->rear=-1;
    return;
}

//Entry queue
bool EnQueue(QuType *&q, Box e)
{
    //if full?
    if(q->rear==MaxSize-1)
        return false;
    q->rear++;
    q->data[q->rear]=e;
    return true;
}

//Leave queue
bool DeQueue(QuType *&q, Box &e)
{
    // if empty
    if(q->front==q->rear)
        return false;
    q->front++;
    e=q->data[q->front];
    return true;
}

// judge empty
bool EmptyQueue(QuType *q)
{
    return(q->rear==q->front);
}
// Destroy queue
void DestroyQueue(QuType *&q)
{
    free(q);
}

void print(QuType *q,int front)
{

    //stack<Box> s;
    int k=front,j,ns=0;
    //cout<< k <<endl;
    /*
    while(k>0)
    {
        printf("k:%d (%d,%d) pre:%d\n",k,q->data[k].i,q->data[k].j,q->data[k].pre);
        k--;
    }
    */
    do
    {
        j=k;
        k=q->data[k].pre;
        //cout<< k <<endl;
        q->data[j].pre=-1;
    }while(k!=0);
    //return;
    printf("一条迷宫路径如下: \n");
    k=0;
    while(k<MaxSize)
    {
        if(q->data[k].pre==-1)
        {
            ns++;
            printf("\t(%d,%d)",q->data[k].i,q->data[k].j);
            if(ns%5==0)
                printf("\n");
        }
        k++;
    }
    printf("\n");

    /*
    int k=front;
    while(q->data[front].pre!=-1)
    {
        //s.push(q->data[front]);
        q->data[front+1].pre=-1;
        q->front=q->data[front].pre;
    }
    //s.push(q->data[1]);
    printf("the least path of map:\n");
    int ns=1;
    while(!s.empty())
    {
        //s.pop();
        ns++;
        //printf("%\t(%d,%d)",e.i,e.j);
        if(ns%5==0)
            printf("\n");
    }
    */
    printf("Length:%d",ns);
}
void myprint(QuType *q,int front)
{
    stack<Box> s;
    while(q->front!=-1)
    {
        s.push(q->data[q->front]);
        q->front=q->data[q->front].pre;
    }
    printf("一条迷宫路径如下:\n");
    int ns=0;
    while(!s.empty())
    {
        Box e=s.top();
        s.pop();
        ns++;
        printf("\t(%d,%d)",e.i,e.j);
        if(ns%5==0)
            printf("\n");
    }
    printf("\nLength:%d\n",ns);
}

bool mgpath(int x,int y,int ex,int ey)
{
    Box e;
    //use a queue
    QuType *q;
    InitQueue(q);
    // enter queue
    e.i=x;
    e.j=y;
    e.pre=-1;
    EnQueue(q,e);
    mg[x][y]=-1;
    while(!EmptyQueue(q))
    {
        DeQueue(q,e);
        //cout<< e.i << e.j<<endl;
        //break;
        //出错重灾区,遍历应该用新的变量
        int il=e.i,jl=e.j;
        if(il==ex && jl==ey)
        {
            //print(q,q->front); //书本例题 感觉太浪费了
            myprint(q,q->front);
            DestroyQueue(q);
            return true;
        }
        for(int i=0;i<4;i++)
        {
            //cout<<next[i][0]<<","<<next[i][1]<<endl;
            int xi=il + next[i][0];
            int yi=jl + next[i][1];
            //cout<< xi << "," <<yi <<endl;
            if(mg[xi][yi]==0)
            {
                //cout<< xi <<","<< yi<<endl;
                e.pre=q->front;
                e.i=xi;
                e.j=yi;
                EnQueue(q,e);
                mg[xi][yi]=-1;
            }
        }
    }
    DestroyQueue(q);
    return false;
}

int main()
{
    int sx=1,sy=1,ex=8,ey=8;// start point and end point
    if(!mgpath(sx,sy,ex,ey))
        printf("can't solve this problem!");
    return 0;
}

0x3 结果

image-20190408180228727

0x4 总结

​ 这个BFS我调试了3.4个小时,原因竟然是在for循环遍历外圈的时候,没有新建变量去接收int new=e.i+next[i][0]导致变量被覆盖,一直没解出结果,归根到底还是自己学的太水了。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Java线程池

前言 Java中对线程池的抽象是ThreadPoolExecutor类,Executors是一个工具类,内置了多种创建线程池的方法: newFixedThreadPool:固定长度线程池 newCachedThreadPool :可缓存线程池 newSin...

nullpointerxyz
31分钟前
35
0
Python笔记:用Python制作二维码

这些年,二维码在我国的日常使用频率特别大。因为其具有简单及安全性吧!除了用网络工具制作二维码,其实用JavaScript或Python也可以制作二维码,而且更有个性。 示例一(制作普通黑白二维码...

tengyulong
43分钟前
0
0
Redis-初体验/数据结构

定义: Redis 是 C 语言开发的一个开源的(遵从 BSD 协议)高性能键值对(key-value)的内存数据库,可以用作数据库、缓存、消息中间件等。它是一种 NoSQL(not-only sql,泛指非关系型数据库...

心田已荒
46分钟前
15
0
如何在保留订单的同时从列表中删除重复项? - How do you remove duplicates from a list whilst preserving order?

问题: Is there a built-in that removes duplicates from list in Python, whilst preserving order? 是否有内置的程序在保留顺序的同时从Python列表中删除重复项? I know that I can us...

fyin1314
今天
29
0
以太坊智能合约开发常见的10个安全问题

本文介绍CheckMarx安全研究小组通过扫描公开的以太坊智能合约所发现的Solidity智能合约开发中常见的十大安全问题,其中__未检查的外部调用__ 和 高成本循环 分列排行榜前两名。该安全问题排行...

区块链教程
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部