迷宫——1.00

2024-02-20 07:58
文章标签 迷宫 1.00

本文主要是介绍迷宫——1.00，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！ 

迷宫：
#############
##I@@@#@#@@@#
###@#@@@#@#@#
#@##@@#@@@#@#
###@@@#@#@#@#
#@@@#@@@#@#@#
#@#@#####@#@#
#@#@@@@@@@@##
#@####@#@#@@#
#@#@@#@@#@#@#
###@#@###@@@#
#@@##@###@###
########O@###
MAIN.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#include "mazeSolution.h"/**主函数(仅限测试)---程序入口**/
int main(void)
{Maze *M = new Maze("D:\\DataStructures\\maze\\MazeStack\\MazeStack\\Maze.txt");//迷宫图的设定文件，路径可以自定义M->DisplayMazeGraphic();if(M->FindMazePath()){cout<<"You can find the route!"<<endl;M->Format();M->DisplayMazeGraphic();}else//没有发现可以走出迷宫的方法cout<<"No solution!"<<endl;delete M;system("pause");return 0;
}

mazeStack.h
#ifndef MAZESTACK_H
#define MAZESTACK_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10#define UPON  0
#define RIGHT 1
#define DOWN  2
#define LEFT  3
#define TRIED 4#define MALLOC_JUDGE(E) if(!E){fprintf(stderr,"内存分配失败……");\system("pause");\exit(EXIT_FAILURE);\
}
///========================struct===============================
struct coordinate
{int x,y;
};struct position
{char sign[20];//做标记，看是墙还是路---(走出迷宫的方向)int dir;//下一个可以走的方向struct coordinate pos;//记录所处的坐标位置
};///====================stack class====================
typedef struct position SElemType;class SqStack
{
private:SElemType *base;SElemType *top;int stackSize;
public:SqStack();                //InitStackbool ClearStack();        //clear stackbool StackEmpty();        //judge emptybool DestoryStack();      //destory stackbool GetTop(SElemType &e);//get the top of the stackbool Push(SElemType e);   //入栈pushbool Pop(SElemType &e);   //出栈popbool StackTraverse(void(*visit)());//Traverseint StackLength();        //get the length of the stackprotected:
};SqStack::SqStack()
{base = (SElemType*)calloc(STACK_INIT_SIZE,sizeof(SElemType));MALLOC_JUDGE(base);//";"可以省略top = base;stackSize = STACK_INIT_SIZE;
}bool SqStack::GetTop(SElemType &e)
{if(base == top)return false;elsee = *(top - 1);return true;
}bool SqStack::Push(SElemType e)//入栈
{if(top - base >= stackSize){//栈满，追加存储空间base = (SElemType*)realloc(base,(STACK_INIT_SIZE + STACKINCREMENT)*sizeof(SElemType));MALLOC_JUDGE(base);top = base + stackSize;stackSize += STACKINCREMENT;}*top++ = e;return true;
}bool SqStack::Pop(SElemType &e)//出栈
{if(top == base)//空栈return false;elsee = *--top;return true;
}bool SqStack::StackEmpty()
{if(base == top)return true;elsereturn false;
}bool SqStack::DestoryStack()
{if(base == NULL)return false;free(base);base = top = NULL;stackSize = 0;return true;
}#endif MAZESTACK
 
#ifndef MAZESOLUTION_H
#define MAZESOLUTION_H#include <iostream>
#include <fstream>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;#include "mazeStack.h"#define MAX_SIZE 18//迷宫的长宽值(length,width)不大于18class Maze: public SqStack
{
private:int length,width;struct position mazeGraphic[MAX_SIZE][MAX_SIZE];struct coordinate inlet,outlet;
public:Maze(char *Maze);void DisplayMazeGraphic();bool NextPos(struct position &e1,struct position &e2);bool CanPass(struct position e1,struct position &e2);bool FindMazePath();void Format();
protected:
};Maze::Maze(char *Maze) 
{fstream fin;fin.open(Maze,ios::in);if(!fin){fprintf(stderr,"打开文件操作失败……");system("pause");exit(EXIT_FAILURE);}else{int i = 0,j = 0;char cTemp;length = width = 0;while((cTemp = fin.get()) != EOF){mazeGraphic[i][j].dir = UPON;mazeGraphic[i][j].pos.x = j;mazeGraphic[i][j].pos.y = i;switch(cTemp){case '#':strcpy(mazeGraphic[i][j++].sign,"■");//墙break;case '@':strcpy(mazeGraphic[i][j++].sign,"□");//路break;case 'I':inlet = mazeGraphic[i][j].pos;strcpy(mazeGraphic[i][j++].sign,"★");//入口break;case 'O':outlet = mazeGraphic[i][j].pos;strcpy(mazeGraphic[i][j++].sign,"☆");//出口break;case '\n':j = 0,i++;length++;break;default:fprintf(stderr,"未知错误！操作失败……\n");system("pause");exit(EXIT_FAILURE);}if(width < j)width = j;}}fin.close();
}//打印迷宫布局
void Maze::DisplayMazeGraphic()
{for(int i = 0;i < length;++i){for(int j = 0;j < width;++j)cout<<mazeGraphic[i][j].sign;cout<<endl;}
}bool Maze::CanPass(struct position e1,struct position &e2)
{bool _bool = true;int i = e1.pos.x;//right & leftint j = e1.pos.y;//upon & downint _dir = e1.dir;switch(_dir){case UPON:if(j > 0 && strcmp(mazeGraphic[j - 1][i].sign,"■") != 0)e2 =  mazeGraphic[j - 1][i];	else_bool = false;break;case RIGHT:if(i + 1 < width && strcmp(mazeGraphic[j][i + 1].sign,"■") != 0)e2 =  mazeGraphic[j][i + 1];else_bool = false;break;case DOWN:if(j + 1 < length && strcmp(mazeGraphic[j + 1][i].sign,"■") != 0)e2 =  mazeGraphic[j + 1][i];else_bool = false;break;case LEFT:if(i > 0 && strcmp(mazeGraphic[j][i - 1].sign,"■") != 0)e2 =  mazeGraphic[j][i - 1];else_bool = false;break;default:fprintf(stderr,"未知错误！操作失败……\n");system("pause");exit(EXIT_FAILURE);}return _bool;
}//寻找下一个可以通过的路口
bool Maze::NextPos(struct position &e1,struct position &e2)
{while(e1.dir != TRIED){e1.dir++;mazeGraphic[e1.pos.y][e1.pos.x].dir = e1.dir;if(CanPass(e1,e2))return true;}return false;
}//寻找走出迷宫的路径
bool Maze::FindMazePath()
{strcpy(mazeGraphic[inlet.y][inlet.x].sign,"■");Push(mazeGraphic[inlet.y][inlet.x]);struct position e1,e2;while(!StackEmpty()){GetTop(e1);if(NextPos(e1,e2))//找到一个可以走的路口{strcpy(mazeGraphic[e2.pos.y][e2.pos.x].sign,"■");Push(e2);if(!strcmp(e2.sign,"☆"))break;}else{Pop(e1);strcpy(mazeGraphic[e1.pos.y][e1.pos.x].sign,"□");}}if(!StackEmpty())return true;elsereturn false;
}//格式化---提供一种输出迷宫路径的方式
//销毁栈
void Maze::Format()
{struct position e;Pop(e);while(Pop(e)){int i = e.pos.x,j = e.pos.y;switch(mazeGraphic[j][i].dir){case UPON:strcpy(mazeGraphic[j][i].sign,"↑");break;case RIGHT:strcpy(mazeGraphic[j][i].sign,"→");break;case DOWN:strcpy(mazeGraphic[j][i].sign,"↓");break;case LEFT:strcpy(mazeGraphic[j][i].sign,"←");break;default:fprintf(stderr,"未知错误！操作失败……\n");system("pause");exit(EXIT_FAILURE);}}strcpy(mazeGraphic[inlet.y][inlet.x].sign,"★");strcpy(mazeGraphic[outlet.y][outlet.x].sign,"☆");DestoryStack();
}#endif MAZESOLUTION_H














                                    

                                        这篇关于迷宫——1.00的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
                                    

                                    

                                

                            

                            

                        

                    

                    

                        

                            

                            http://www.chinasem.cn/article/727515。
                            
                        

                    

                    
                    

                        
                            
                        
                    

                

                

                    相关文章
                

                    

                        

                            

                                

                                    
                                        nyoj306(走迷宫)
                                    
                                

                            

                            

                                

                                    nyoj306(走迷宫)
                                

                                

                                    走迷宫 时间限制： 1000 ms  |  内存限制： 65535 KB  难度：5   描述 Dr.Kong设计的机器人卡多非常爱玩，它常常偷偷跑出实验室，在某个游乐场玩之不疲。这天卡多又跑出来了，在SJTL游乐场玩个不停，坐完碰碰车，又玩滑滑梯，这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出，方阵中单元格中填充了一个整数，表示走到这个位置的难度。 这个迷宫可以向上走，向
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        《GOF设计模式》—抽象工厂(Abstract Factory)—Delphi源码示例：基于抽象工厂的迷宫
                                    
                                

                            

                            

                                

                                    《GOF设计模式》—抽象工厂(Abstract Factory)—Delphi源码示例：基于抽象工厂的迷宫
                                

                                

                                          示例：基于抽象工厂的迷宫     实现：     如果TMaze.Create是传递一个对象当作参数来建立rooms、walls及doors；如此你可以以不同的参数来改变rooms、walls及doors的类。  请注意MazeFactory也就是工厂方法(Factory Method)的一个集合；这是最通常实现抽象工厂模式的方式。同时请注意MazeFactory不是一个抽象类
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        走迷宫变体【拼多多1面0905】
                                    
                                

                            

                            

                                

                                    走迷宫变体【拼多多1面0905】
                                

                                

                                    题目大致描述:  有一个N*M的迷宫，主角被放在随机的位置上，给你一个函数，控制主角逃离迷宫。 可以使用的函数：int move(String direction) (//direction代表上下左右四个方向，分别是“U"、“D"、“L"、“R"//返回值有3种，包括-1、0、1；-1表示前面是陷阱或墙，主角不能往前走，会留在原地；0表示迷宫出口，恭喜成功逃离；1表示前面可以走，主角前进一格）
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        FZU1205/SDUT1157_小鼠迷宫问题(DFS+BFS)
                                    
                                

                            

                            

                                

                                    FZU1205/SDUT1157_小鼠迷宫问题(DFS+BFS)
                                

                                

                                    解题报告 http://blog.csdn.net/juncoder/article/details/38146041  题目传送门 题意 求最短路和最短路的路数。 思路： BFS+DFS，先求出最短路。在DFS搜等于最短路的条数。 不加优化SDUTOJ过了，数据就是水。 确定了最短路的长度，加上奇偶剪枝FOJ也过了。  #include <queue>#include <c
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        A*算法解决迷宫寻路问题
                                    
                                

                            

                            

                                

                                    A*算法解决迷宫寻路问题
                                

                                

                                    A*算法解决迷宫寻路问题 问题描述 下图是一个迷宫，试为机器人找一条从Start到End的最短路径设计一搜索算法  设计思路 a)状态空间的表示 首先将迷宫图转换为列表形式呈现，每个格子用 （横坐标，纵坐标，上通路状态，下通路状态，左通路状态，右通路状态）来表示，通路状态用1或0表示，可通过为1，不可通过为0。比如起点（1，1），假定不能从起点出去，所以（1,1）可以走下或走右，所以第一格
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        两种迷宫生成算法
                                    
                                

                            

                            

                                

                                    两种迷宫生成算法
                                

                                

                                    这里要介绍两种迷宫生成的算法，Recursive Backtracking和Eller’s Algorithm。它们都生成的是Perfect maze，也就是说每个区域都连通，并且没有环的迷宫。  我们现在说Recursive backtracking：   迷宫的初始状态是墙壁都存在。选择一个开始区域。  随机得选择一个没有访问过的邻接区域，并打通与它之间的墙壁。此邻接区域称为当前区域。
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        深度优先遍历之迷宫生成算法
                                    
                                

                            

                            

                                

                                    深度优先遍历之迷宫生成算法
                                

                                

                                    1、图的深度优先遍历简介          例如，要遍历上面这个图   采取深度优先算法(从1开始)   准备一个Stack s，预定义三种状态：A未被访问 B正准备访问 C已经访问   一、访问1，把它标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问   此时系统状态：   已经被访问的点：1   还没有被访问的点：3 4
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        HDU1269 迷宫城堡 （强连通图判定）
                                    
                                

                            

                            

                                

                                    HDU1269 迷宫城堡 （强连通图判定）
                                

                                

                                    题意：判定给出的有向图是不是强连通图  Tarjan算法模板题目 #include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<set>#include<map>#include<string>#include<cstring>#include<stack>#include<queue
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        【并查集】 HDU 1272 小希的迷宫
                                    
                                

                            

                            

                                

                                    【并查集】 HDU 1272 小希的迷宫
                                

                                

                                    HDU 1272 小希的迷宫 需要判断是否是连通图。  #include <iostream>#include <string>#include <algorithm>#include <math.h>#include <stdio.h>#include <cstring>#include <stdlib.h>using namespace std;int father[100
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        [BFS广度优先搜索] 迷宫
                                    
                                

                            

                            

                                

                                    [BFS广度优先搜索] 迷宫
                                

                                

                                    描述 给定一个仅由数字 0 与 1 组成的 n 行 m 列的迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的任意一格 1 上；同样地，若你位于一格 1 上, 那么你可以移动到相邻 4 格中的任意一格 0 上。  现在，有 q 次询问。每次询问从给定的某一格 (第 x 行，第 y 列，均从 0 开始标号) 开始，在规则内任意移动。这样，有一些格子是可能到达的，而其余格子是无法到达的
                                

                                

                                    阅读更多...
                                

                            

                        

                    

            

        

    


    


    

        

            Copyright China编程   23002807@qq.com
        

        

            沪ICP备2023033072号-2