迷宫寻迹算法
❶ 回溯算法的基本思想
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
❷ c语言走迷宫dfs用了迷宫，其中有回溯思想，就是走不通返回上一状态，
递归了吧。使用了系统栈，在递归结束时用了返回。根据栈的先进后出原则，就是一步步的在回溯了。
❸ C语言编程求解啊！利用回溯算法的迷宫搜索类型问题
#include "stdafx.h"
#include <iostream>
#include "cmath"
#include <fstream>
using namespace std ;
int ROW ;
int COL ;
int **g_pRoom ;
// 回溯法注意标记已访问过的节点。。。。。不然就会进入重复操作将栈用空。。。。。。。。
struct Point
{
Point( int xx = 0, int yy = 0 ):x(xx),y(yy) { }
int x ;
int y ;
} ;
int g_nMax = 0 ;
Point g_pResult[100] ;
int g_nCount ;
Point g_pStart ;
Point g_pEnd ;
Point g_pOrient[4] = { Point(-1, 0 ) , Point( 0 ,1 ) , Point( 1 ,0 ) , Point( 0 , -1 ) } ;
bool Read_data( ifstream &file )
{
if( file.eof() )
return false ;
g_nMax = 0 ;
g_nCount = 0 ;
file>>ROW>>COL ;
g_pRoom = new int*[ROW] ;
g_pStart = g_pEnd = Point( -1, -1 ) ;
for( int i = 0 ; i < ROW ; i++ )
g_pRoom[i] = new int[COL] ;
for( int i = 0 ; i < ROW ; i++ )
for( int j = 0 ; j < COL ; j++ )
{
file>>g_pRoom[i][j] ;
if( g_pRoom[i][j] == -1 )
{
g_pStart.x = j ;
g_pStart.y = i ;
}
else if( g_pRoom[i][j] == -2 )
{
g_pEnd.x = j ;
g_pEnd.y = i ;
}
}
if( g_pStart.x == -1 || g_pEnd.x == -1 )
{
cout<<" the data errror !\n" ;
return false ;
}
return true ;
}
void Dateback( Point pStart )
{
static Point Stack[1000] ;
static int nTop = 0 ;
static int Apple = 0 ;
if( pStart.x == g_pEnd.x && pStart.y == g_pEnd.y )
{
if( Apple + 2 > g_nMax )
{
g_nMax = Apple + 2 ;
for( int i = 0 ; i < nTop ; i++ )
g_pResult[i] = Stack[i] ;
g_nCount = nTop ;
} // ....
}
else
{
for( int i = 0 ; i < 4 ; i++ )
{
Point s ;
s.x = pStart.x + g_pOrient[i].x ;
s.y = pStart.y + g_pOrient[i].y ;
if( s.x >= 0 && s.x < COL && s.y >= 0 && s.y < ROW && g_pRoom[s.y][s.x] != 0 )
{
Apple += g_pRoom[s.y][s.x] ;
Stack[nTop++] = s ;
int temp = g_pRoom[s.y][s.x] ;
g_pRoom[s.y][s.x] = 0;
Dateback( s ) ;
nTop-- ;
g_pRoom[s.y][s.x] = temp ;
Apple -= g_pRoom[s.y][s.x] ;
}
}
}
}
int main()
{
ifstream file("data.txt") ;
Read_data(file) ;
Dateback( g_pStart ) ;
cout<<g_nMax ;
cout<<"("<<g_pStart.y<<","<<g_pStart.x<<")"<<" " ;
for( int i = 0 ; i < g_nCount ; i++ )
cout<<"("<<g_pResult[i].y<<","<<g_pResult[i].x<<")"<<" " ;
return 0 ;
}
❹ 怎么用回溯法来实现迷宫问题,其中用'*'来表示墙,用A来表示路径!!1
爱莲说
（宋）周敦颐
水陆草木之花，可爱者甚蕃。晋陶渊明独爱菊；自李唐来，世人盛爱牡丹；予独爱莲之出淤泥而不染，濯清涟而不妖，中通外直，不蔓不枝，香远益清，亭亭净植，可远观而不可亵玩焉。予谓菊，花之隐逸者也；牡丹，花之富贵者也；莲，花之君子者也。噫！菊之爱，陶后鲜有闻；莲之爱，同予者何人；牡丹之爱，宜乎众矣。
[注释]：
(1)爱莲说：选自《周元公集》。作者周敦颐着名的唯心主义哲学家。“说”，是古代论说文的一种体裁，可以说明事物，也可以论述道理。
(2)蕃：多。
(3)晋陶渊明独爱菊：陶渊明(365-427)，一名潜，字符亮，东晋浔阳(现在江西省九江县)人，着名的诗人。他很爱菊花，常在诗里写到，如《饮酒》诗里的“采菊东篱下，悠然见南山”，向来称为名句。
(4)自李唐来，世人甚爱牡丹：唐朝以来，人们很爱牡丹。李唐，指唐朝。唐朝的皇帝姓李，所以称为“李唐”。世人，社会上的一般人。唐人爱牡丹，古书里有不少记载，如唐朝李肇的《唐国史补》里说：“京城贵游，尚牡丹……每春暮，车马若狂……种以求利，一本(一株)有直(同“值”)数万(指钱)者。”
(5)予独爱莲之出淤泥而不染：我单单喜欢莲花，喜欢它从污泥里生出却不被沾染。淤泥，池塘里积存的污泥。
(6)濯(zhuó)清涟而不妖：在清水里洗过却不妖艳。濯，洗涤。清涟，水清而有微波的样子，这里指清水。妖，美丽而不端庄。
(7)不蔓不枝：不牵牵连连的，不枝枝节节的。
(8)香远益清：香气越远越清。益，更，越。
(9)亭亭：耸立的样子。
(10)亵(xiè)玩：玩弄。亵，亲近而不庄重。
(11)隐逸者：隐居的人。封建社会里，有些人不愿意跟统治者同流合污，便隐居避世。
(12)牡丹，花之富贵者也：牡丹是花中的“富人”。
(13)君子：道德高尚的人。
(14)噫(yī)：叹词，相当于“唉”。
(15)菊之爱：对于菊花的爱好。
(16)鲜(xiǎn)有闻：很少听到。鲜，少。
(17)宜乎：宜，当，这里和“乎”连用，有“当然”的意思。
[译文]：水上地上各种草和木的花，可爱的是很多的。晋朝陶渊明唯独喜爱菊花。从唐朝以来，世上的人们非常喜爱牡丹。我唯独喜爱莲花，它从污泥中长出来，却不受到污染，在清水里洗涤过但是不显得妖媚，它的茎中间贯通，外形挺直，不牵牵连连，不枝枝节节的，香气远播，更加清香，笔直地洁净地立在那里，可以远远地观赏但是不能贴近去轻慢地玩弄啊。
我认为，菊花是花中的隐士；牡丹，是花中的富贵者；莲花，是花中的君子。
唉！爱菊花的人，从陶渊明以后很少听到过。爱莲花的人，像我一样的人还有什么人呢？至于爱牡丹的人，人数当然就很多了！
“说”，古代文体之一，它往往借描绘事物以抒情言志。周敦颐的《爱莲说》正是这种托物言志的文体中一篇不可多得的传世佳作。
[赏析]：周敦颐，北宋人，其人一生澹泊名利，不求闻达。他的这种高洁的人品，诚如北宋文学大家黄庭坚所誉：“人品甚高，胸怀洒落，如光风霁月……”而他的传世散文佳作《爱莲说》恰恰正是他酒落胸怀所透射而出的精神折光。
莲花，是古往今来文人笔下高歌咏叹的对象，但大多数文人都是惊叹于它的清姿素容，并将其形诸笔端；而这笔散文精品却独辟蹊径，通过对莲的形象和品质的描写，歌颂了莲花坚贞的品格，从而也表现了作者洁身自爱的高洁人格和洒落的胸襟。
从内容上看，这篇文章可明显分为二部分：前一部分对莲花高洁的形象极尽铺排描绘之能事；第二部分则揭示了莲花的比喻义，分评三花，并以莲自况，抒发了作者内心深沉的概叹。
文章的前一部分，写出了莲花之美就在于其一个“洁”字。首先，“出淤而不染，濯清莲而不妖”写出了莲花身处污泥之中，却纤尘不染，不随世俗、洁身自爱和天真自然不显媚态的可贵精神；其次，“中通外直，不蔓不枝”，写出了它里外贯通、外表挺直、表里如一、不牵扯攀附的高尚品质；再次“可远观而不可亵玩”，写出了莲如傲然不群的君子一样，决不被俗人们轻慢玩弄。
前文所说的一切，事实上是作者人格的写照，是作者心志的自明，关于这一点，我们可以从文章的第二部分得到明证。正如作者所说：“莲之爱，同予者何人？”其间的潜台词就是感慨于象他一样具有莲花之洁的人实在太少了。
在写法上，《爱莲说》具有“说”这一文体的共同特点，即托物言志。文章从“出淤泥而不染”起，以浓墨重彩描绘了莲的气度、莲的风节，寄予了作者对理想人格的肯定和追求，也反射出作者鄙弃贪图富贵、追名逐利的世态的心理和自己追求洁身自好的美好情操。同时，文章还运用了对比，反衬的手法，在文中几次以菊、牡丹反衬莲之美；还把菊花的隐逸，牡丹的富贵和莲花的高洁相对比，使“爱莲”之一主题得以加深，没有空洞的说教，而是通过三种形象的对比，起到了突出中心，加深立意的作用，手法可谓高明之极。而且，文章以一个“爱”字贯通全文，使得文章结构谨严。 在文章结尾，作者一叹真正隐逸的高士极少，二叹品格高尚的君子罕见，三叹贪慕富贵的俗人很多，耐人寻味，发人深省。
这首诗在语言上也同样富有特色，那就是优美简炼，的确是如莲之美——“不枝不蔓”，没有多余的无用之语
莲花的美丽别称
(1)芙蓉:《尔雅》：“荷，芙蕖，别名芙蓉，亦作芙容。”
(2)芙蕖:《尔雅·释草》：“荷、芙蕖。……其华菡萏，其实莲，其根藕。”
(3)藕花: 唐张籍《送从弟之苏州》诗：“夜月红柑树，秋风白藕花。”
(4)水芙蓉:《群芳谱》：“荷花亦称作芙蕖、水芙蓉。”
(5)草芙蓉:杜诗注云：产于陆者曰木芙蓉，产于水者曰草芙蓉。”
(6) 水花:李时珍《本草纲目》：“莲花”释名：“芙蓉、芙蕖、水华。”
(7)净友又称净客。莲花洁净不染，因此人们称其为净友。
(8)水芝:普崔豹《古今注》下“草木”：“芙蓉一名荷华，一名水目，一名水芝，一名水花。”
(9)泽芝:《类聚》郭璞《尔雅图赞 ·芙蓉赞 》云：“芙蓉丽草，一曰泽芝，……”
(10) 灵草:吴闵鸿《芙蓉赋并序》：“乃有芙蓉灵草，栽育中川。”
(11)玉环:《本草经》载：“荷花又名玉芝。”
(12)君子花:北宋周敦颐着《爱莲说》，谓莲为花中君子，莲又称“君子花”。
(13) 水宫仙子:因莲生水中，莲花亭亭玉立于水面，好似仙女飘然而行，故名。
(14) 菡萏:《尔雅》：“荷，芙蕖……其华菡萏。”
莲花与佛教
据 说 ，释 迦 牟 尼 本 是 天 上 的 菩 萨 ，下 凡 降 生 到 迦 毗 罗 卫 国 净 饭 王 处 。 净 饭 王 的 王 妃 摩 耶 夫 人 , 长 得 象 天 仙 一 样 美 丽 ， 性 情 温 和 贤 淑 ， 与 国 王情 深 似 海 。摩 耶 夫 人 回 忆 新 婚 之 夜 ， 她 朦 胧 中 看 到 远 处 有 一 个 人 骑 着 一头 白 象 向 她 走 来 并 且 逐 渐 变 小 ， 从 她 的 右 肋 处 钻 入 她 的腹 中 。 她 心 中 模 模 糊 糊 地 预 感 到 菩 萨 化 作 一 头 白 象 入 胎。 日 后 ， 身 怀 有 孕 的 摩 耶 夫 人 脸 上 ， 微 微 泛 着 红 晕 ， 那 色 彩 鲜 艳 的 绿 色 领 口 花 边 象 一 片 莲 叶 ， 她 的 脸 儿 象 一 朵 绽 开 的 莲 花 。 后 来 摩 耶 夫 人 在 娑 罗 树 下 降 生 佛 祖 时 ， 百 鸟 群 集 歌 唱 ， 天 乐 鸣 空 相 和 ， 四 季 里 的 花 木 都 一 同 盛 开， 尤 其 是 沼 泽 内 突 然 开 放 出 大 得 象 车 盖 一 样 的 莲 花 。 佛祖 一 出 世 ， 便 站 在 莲 花 上 ， 一 手 指 天 ， 一 手 指 地 ， 并 说： “ 天 上 天 下 ， 惟 我 独 尊 ” 。
不 仅 如 此 ， 莲 还 与 佛 教 医 学 有 着 密 切 关 系 。 莲 花 含 有 丰 富 的 营 养 ， 既 可 食 用 又可 药 用 。 古 代 女 子 常 采 清 晨 带 露 的 莲 花 敷 面 美 容 ， 或 服 食 莲 花 以 养 颜。 莲 花 含 有 皮 素 和 木 樨 素 ，能 润 泽 肤 色 。 初 放 鲜 嫩 的 莲 花 用 开 水 泡 饮 ， 其 汁 翠 绿 清 香 ， 有 清 暑 解 热 和 生 津 开 胃 之 功 效 。 莲 的 地 下 根 茎 称 为 莲 藕 。 相 传 佛 祖 的 十 大 弟 子之 一 舍 利 弗 患 有 肺 结 核 ， 目 犍 连 来 探 望 他 ， 并 得 知 舍 利 弗 喜 欢 吃 莲 藕 ， 就 带 些 新 鲜 莲 藕 让 舍 利 弗 吃 ， 舍 利 弗 吃 莲 藕 后 果 然 病 愈 。 后 来 ， 佛 祖 弟 子 经 常 用 莲 藕 作 为 药 用来 治 病 ， 并 发 现 了 莲 藕 的 许 多 药 用 价 值 。
莲花的美好品质
在千古第一诗人屈原的代表作 《离骚》中有这样的诗句“制芰荷以为衣兮，集芙蓉以为裳。”诗人为了表达自己不与世俗同流合污的决心，要穿上用莲花做成的香气馥郁的衣服。在这里，莲花这一形象，不仅象征着诗人高洁的品质和美好的修养，而且表现了诗人浓烈的激情和奇幻的想象以及《离骚》这首不朽杰作的浪漫主义特色。
“江南可采莲，莲叶何田田。鱼戏莲叶间。鱼戏莲叶东，鱼戏莲叶西，鱼戏莲叶南，鱼戏莲叶北。”这是汉代乐府民歌中的一首极为清新优美的小诗。在这首小诗中，“莲”既指实物花卉莲花，又是爱怜的“怜”谐音，以鱼戏莲叶隐喻男女之间的爱情，极其生动形象。在秀美的江南水乡的大背景中，采莲的男女主人公摇着小舟，自由地歌唱着纯洁美丽的爱情，该是一幅多么清新的图画！
“荷叶罗裙一色裁，芙蓉向脸两边开。乱入池中看不见，闻歌始觉有人来。”在唐代七绝圣手王昌龄的这首《采莲曲》中，采莲少女的美丽虽不着一字，却尽得风流，因为她们的身影已与风光秀丽、如诗如画的荷塘、莲花融为一体了。从这自然浑成、耐人寻味的意境中，我们不难感受到中国古典文学的魅力吧。
代表着南朝乐府民歌最高成就的《西洲曲》，更是对莲花和采莲有着细致入微的描写：“开门郎不至，出门采红莲。采莲南塘秋，莲花过人头。低头弄莲子，莲子青如水。置莲怀袖中，莲心彻底红。忆郎郎不至，仰首望飞鸿……”这首诗中采莲的情形，不仅生动地展示了江南水乡人民的生活，而且写出了采莲女主人公对远行丈夫深深的思念之情，语言清新明丽，意境悠远，情思缠绵。
以“诚斋体”闻名南宋诗坛的着名诗人杨万里的诗《晓出净慈寺送林子方》：“毕竟西湖六月中，风光不与四时同。接天莲叶无穷碧，映日荷花别样红。”在这首诗中，诗人撷取了“接天莲叶”和“映日荷花”两个典型景物，以通俗明快、流转圆活的风格，写出了六月里西湖的美丽风光，一改宋诗瘦硬生涩的弊端，极具自然灵性。
宋朝理学的创导者、哲学家周敦颐的《爱莲说》中有这样的句子：“予独爱莲之出淤泥而不染，濯清涟而不妖，中通外直，不蔓不枝，香远益清，亭亭静植，可远观而不可亵玩焉……莲，花之君子者也。”在这篇托物言志的散文中，作者从不同的角度、不同的方面写尽了莲花的高洁品质、优雅气质、优美的姿态和庄重的仪表，表达了封建士大夫高洁的情操和志趣。自此，莲花便有了灵性，步入花中君子之列。
明代的许仲琳，在其着名的神魔小说《封神演义》中，塑造了一个莲花化身的少年英雄哪咤的形象，他纯真勇敢而又法力高强，敢于蔑视神权、打抱不平，极具正义和反抗精神，是我国古典文学中为人民群众所喜爱的人物形象之一。透过哪咤这一神话人物形象，我们看到莲花又变成了正义和勇敢的化身。
一代散文大师朱自清的美文《荷塘月色》，通过高超的艺术手法和情景交融的意境营造，写出了月下荷塘素淡朦胧的美：“曲曲折折的荷塘上面，弥望的是田田的叶子……，层层的叶子中间，零星地点缀着些白花，有婀娜的开着的，有羞涩的打着朵儿的，正如一粒粒的明珠，又如碧天里的星星，微风过处，送来缕缕清香，仿佛远处高楼上渺茫的歌声似的……”月下的荷叶、荷花和荷塘，在现代作家朱自清的笔下简直就像一幅意境幽美的工笔画
❺ 请教高手C++数据结构回溯算法解，迷宫问题
//迷宫用栈做的
#include "stdio.h"
#include "stdlib.h"
#define INITSIZE 100
#define STACKINCRESMENT 10
#define WALL 9999
struct stack
{
int *base;
int *top;
int size;
};
struct mi
{
int val;
bool tag;
int di;
};
void init_stack(stack *);
void push(stack*,int);
int pop(stack*);
int getop(stack*);
int palace(stack*, mi p[10][10]);
int main()
{
int e;
int ch;
struct mi p[10][10];
for(int i=0;i<10;i++)
{
p[0][i].val = 0;
p[i][0].val = 0;
p[9][i].val = 0;
p[i][9].val = 0;
}
for(int j=1;j<9;j++)
{
for(int k=1;k<9;k++)
{
p[j][k].val = 1;
}
}
p[1][3].val = p[1][7].val =0;
p[2][3].val = p[2][7].val =0;
p[3][5].val = p[3][6].val =0;
p[4][2].val = p[4][3].val = p[4][4].val =0;
p[5][4].val = 0;
p[6][2].val = p[6][6].val =0;
p[7][2].val = p[7][3].val = p[7][4].val =0;
p[7][6].val = p[7][7].val =0;
p[8][1].val = 0;
for(int m=0;m<10;m++)
{
for(int n=0;n<10;n++)
{
printf(" %d ",p[m][n]);
p[m][n].tag =0;
p[m][n].di =0;
}
printf("\n");
}
struct stack *s = (stack*)malloc(sizeof(stack));
init_stack(s);
palace(s, p);
printf("\none path is: \n");
for(int a=0;*s->base<89;s->base++)
{
printf("-a");
printf("%d",*s->base);
}
return 0;
}
void init_stack(stack *s)
{
s->base = (int*)malloc(INITSIZE*sizeof(stack));
if(!s->base) printf("malloc error:");
*s->base++ = 0;//栈底为0
s->top = s->base;
s->size = INITSIZE;
}
void push(stack* s, int e)
{
if(s->top - s->base >= INITSIZE)
{
s->base = (int*)realloc(s->base,(s->size+STACKINCRESMENT)*sizeof(stack));
s->top = s->base + s->size;
s->size += STACKINCRESMENT;
}
*s->top++ = e;
}
int pop(stack* s)
{
if(s->top == s->base) printf("error\n");
int e = 0;
e = *--s->top;
*s->top = NULL;
return e;
}
int getop(stack* s)
{
if(s->top == s->base) printf("error\n");
int e = 0;
stack *p = s;
e = *(--p->top);
++p->top;
return e;
}
int palace(stack* s, mi p[10][10])
{
int i=1;
int j=1;
int k;
int r;
push(s,i*10+j);
j++;
do
{
r=getop(s);
if(r==88) return 0;
if(p[i][j].val>0 && p[i][j].di<1)
{
push(s,i*10+j);
p[i][j].tag = 1;
p[i][j].di = 1;
j++;
}
else
{
k = getop(s);
i = k/10;
j = k%10;
if(p[i][j].di==1 && (p[i][j].val>0))
{
p[i][j].di++;
i++;
}
if(p[i][j].di==2 && (p[i][j].val>0))
{
p[i][j].di++;
j--;
if(p[i][j].di>0) { k = pop(s);}
}
}
}while(1);
}
❻ 谁能解释一下回溯算法
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
初识回溯算法是在解决8皇后问题时候，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了
回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。
❼ c++迷宫回溯算法问题 为什么一地次执行if（ok!=1） mase[x][y]=0;这条语句后没有返回main函数
你这个是递归算法啊，当它第一次运行完后，肯定是返回上一次递归进来的地方啦
❽ 请问什么是回溯算法
回溯（backtracking）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图(迷宫问题)或树(N皇后问题)。
一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。
回溯方法的步骤如下：
1) 定义一个解空间，它包含问题的解。
2) 用适于搜索的方式组织该空间。
3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。
回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。
❾ 求走迷宫问题的算法，要求用非递归回溯的方法写
public class MyMaze { private class Point { //自定义数组下标记录类型 int x = 0;
int y = 0; public Point() {
this(0, 0);
} public Point(int x, int y) {
this.x = x;
this.y = y;
} public boolean equals(Point p) {
return (x == p.x) && (y == p.y);
} @Override
public String toString() {
return "(" + x + "," + y + ")";
}
} private int[][] maze = null; //迷宫图
private java.util.Stack<Point> stack = new java.util.Stack<Point>();
//保存路径的栈 public MyMaze(int[][] maze) {
this.maze = maze;
} public void go() {
Point out = new Point(maze.length-1, maze[0].length-1); //出口
Point in = new Point(0,0); //入口
Point curNode = in; //当前点为入口
Point nextNode = null; //下一个访问点(目标点) while(!curNode.equals(out)) {
nextNode = new Point(curNode.x,curNode.y); //设置目标点为当前点，便于下面偏移
if((curNode.x+1)<maze.length&&maze[curNode.x+1][curNode.y]==0) { //如果下方是空的，则目标点向下偏移
nextNode.x++;
} else if((curNode.y+1)<maze[0].length&&maze[curNode.x][curNode.y+1]==0) { //如果右边是空的，则目标点向右偏移
nextNode.y++;
} else if((curNode.x-1)>=0&&maze[curNode.x-1][curNode.y]==0) { //如果上方是空的，则目标点向上偏移
nextNode.x--;
} else if((curNode.y-1)>=0&&maze[curNode.x][curNode.y-1]==0) { //如果左边是空的，则目标点向左偏移
nextNode.y--;
} else { //这里是没有路的状态
maze[curNode.x][curNode.y] = 3; //标记为死路
if(stack.isEmpty()) { //判断栈是否为空
System.out.println("Non solution");
return;
}
curNode = stack.pop(); //弹出上一次的点
continue; //继续循环
} //如果有路的话会执行到这里
stack.push(curNode); //当前点压入栈中
maze[curNode.x][curNode.y] = 2; //标记为已走
curNode = nextNode; //移动当前点
} if(nextNode.equals(out)) {
stack.push(nextNode); //将出口点添加到当前路劲中
maze[nextNode.x][nextNode.y] = 2; //标记为已走
}
System.out.println("\n该迷宫的一条可行路劲为：");
System.out.println("\n"+stack);
} public static void main(String[] args) {
int[][] maze = {
{ 0, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 0, 1, 0, 0 }
};
new MyMaze(maze).go();
}
}
❿ 迷宫回溯
学c的路过，表示看不懂