回溯法也称试探法,这种方法将问题的候选解按某种顺序逐一枚举和检验, 当发现当前的候选解, 不是解时, 就放弃它而选择下一个候选解, 如果当前的候选解, 除了不满足问题规模要求外, 其他所有要求都已满足, 则扩大当前候选解的规模, 继续试探. 如果当前候选解满足了包括问题在内的所有要求, 则这个候选解, 将成为问题的一个解.
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#pragma once
#define M 12
#define P 15
struct offsets
{
int a,b;
char *dir;
};
offsets move[8]={{-1,0,"N"},{-1,1,"NE"},{0,1,"E"},{1,1,"SE"},
{1,0,"S"},{1,-1,"SW"},{0,-1,"W"},{-1,-1,"NW"}};
int Maze[M+2][P+2]={
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
{1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
{1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
{1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},
{1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
{1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
{1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
{1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1},
{1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
{1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
};
int mark[M+2][P+2];
int SeekPath(int x,int y)
{
int i,g=0,h=0; char *d;
if(x==M&&y==P+1)
return 1;
for(i=0;i<8;i++)
{
g=x+move[i].a;
h=y+move[i].b;
d=move[i].dir;
if(Maze[g][h]==0&&mark[g][h]==0)
{
mark[g][h]=1;
if(SeekPath(g,h))
{
cout<<"("<<g<<","<<h<<"),"<<"Direction:"<<d<<","<<endl;
return 1;
}
}
}
if(x==1&&y==1)
cout<<"No path in the Maze"<<endl;
return 0;
}
分享到:
相关推荐
数据结构走迷宫算法,学习了他人的之后自己写的程序,运行OK
该程序框图是迷宫问题求解的形象描述,通过该框图可以很好的了解上一篇源代码的内容
VC++2012编程演练数据结构《8》回溯法解决迷宫问题
迷宫-回溯法改进(优先级算法)
数据结构课程设计java求解迷宫,回溯法,A算法.docx
迷宫的存储结构以二维数组来存储,用0,1表示通或不通。表面上似乎迷宫问题是一种特殊问题的解决方法,其实迷宫问题是一种特殊形式图的问题,因此,迷宫总量可...本文采用回溯法求解迷宫路径,算法用到数据结构中的栈。
数据结构课程设计,使用了回溯法和A*算法,求解迷宫。有代码和文档,另附A*算法教程
求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可以到达,则到达新点,否则试探下一方向;若所有的方向均没有通路,则沿原路...
大家一起学习,了解利用回溯法求解迷宫,利用windows下的颜色的设定和定位,希望对大家有所帮助
所谓的回溯技术就是像人走迷宫一样,先选择一个前进方向尝试,一步步往前试探,在遇到死胡同不能再往前的时候就回退到上一个分叉点,选另一个方向尝试,而在前进和回撤的路上都设置一些标记,以便能正确返回,直到...
用c++写的通用算法,回溯法 用于解决迷宫,八皇后问题,具有通用性
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
数据结构课程设计题目,课程设计,C语言!
《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参考教材。本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论查找和排序的...
数据结构3.txt 数组完全单元.txt 数组操作.txt 数组递归退出.txt 数组递归退出2.txt 文件加密.txt 文件复制.txt 文件连接.txt 无向图.txt 时间陷阱.txt 杨辉三角形.txt 栈单元加.txt 栈操作.txt 桃子...
leetcode迷宫问题 ...对于迷宫问题,即多个步骤组成的问题,并且每一个问题都有多个选项(类似树结构),可以使用回溯法。如果叶节点不满足条件,则回溯到它的上一个节点,尝试其他选项。多使用两个函
在我国学习计算机的人中很少有不知道谭浩强教授的。他善于用容易理解的方法和语言说明复杂的概念。许多人认为他开创了计算机书籍贴近大众的新风,为我国的计算机普及事业做出了重要的贡献。 谭浩强教授曾获全国高校...
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
8. (注:提高可不做)栈的应用3(可使用顺序栈或链栈完成):使用递归的回溯法实现迷宫程序(提示:程序分为两大模块,根据数据生成地图,漫游地图) 9.定义并实现循环队列的数据结构。 10.应用队列完成Johnson...