【算法】老鼠走迷宫

老鼠走迷官(一)

说明老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙壁,使用1来表 示老鼠的行走路径,试以程式求出由入口至出口的路径。 解法老鼠的走法有上、左、下、右四个方向,在每前进一格之后就选一个方向前进,无法前 进时退回选择下一个可前进方向,如此在阵列中依序测试四个方向,直到走到出口为止,这是 递回的基本题,请直接看程式应就可以理解。 #include <stdio.h> #include <stdlib.h> int visit(int, int); int maze[7][7] = {{2, 2, 2, 2, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 2}, {2, 0, 2, 0, 2, 0, 2}, {2, 0, 0, 2, 0, 2, 2}, {2, 2, 0, 2, 0, 2, 2}, {2, 0, 0, 0, 0, 0, 2}, {2, 2, 2, 2, 2, 2, 2}}; int startI = 1, startJ = 1; // 入口 int endI = 5, endJ = 5; // 出口 int success = 0; int main(void) { int i, j; printf("显示迷宫:\n"); for(i = 0; i < 7; i++) { for(j= 0; j < 7; j++) if(maze[i][j] == 2) printf("█"); else printf(" "); printf("\n"); } if(visit(startI, startJ) == 0) printf("\n没有找到出口!\n"); else { printf("\n显示路径:\n"); for(i = 0; i< 7; i++) { for(j = 0; j < 7; j++) { if(maze[i][j] == 2) printf("█"); else if(maze[i][j] == 1) printf("◇"); else printf(" "); } printf("\n"); } } return 0; } int visit(int i, int j) { maze[i][j] = 1; if(i == endI && j == endJ) success = 1; if(success != 1 && maze[i][j+1] == 0)visit(i, j+1); if(success != 1 && maze[i+1][j] == 0)visit(i+1, j); if(success != 1 && maze[i][j-1] == 0)visit(i, j-1); if(success != 1 && maze[i-1][j] == 0)visit(i-1, j); if(success != 1) maze[i][j] =0; return success; }

老鼠走迷官(二) 说明由于迷宫的设计, 老鼠走迷宫的入口至出口路径可能不只一条, 如何求出所有的路径呢? 解法求所有路径看起来复杂但其实更简单,只要在老鼠走至出口时显示经过的路径,然后退 回上一格重新选择下一个位置继续递回就可以了,比求出单一路径还简单,我们的程式只要作 一点修改就可以了。 #include <stdio.h> #include <stdlib.h> void visit(int, int); int maze[9][9] = {{2, 2, 2, 2, 2, 2, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 0, 0, 2}, {2, 0, 2, 2, 0, 2, 2, 0, 2}, {2, 0, 2, 0, 0, 2, 0, 0, 2}, {2, 0, 2, 0, 2, 0, 2, 0, 2}, {2, 0, 0, 0, 0, 0, 2, 0, 2}, {2, 2, 0, 2, 2, 0, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 0, 0, 2}, {2, 2, 2, 2, 2, 2, 2, 2, 2}}; int startI = 1, startJ = 1; // 入口 int endI = 7, endJ = 7; // 出口 int main(void) { int i, j; printf("显示迷宫:\n"); for(i = 0; i < 7; i++) { for(j = 0; j <7; j++) if(maze[i][j] == 2) printf("█"); else printf(" "); printf("\n"); } visit(startI, startJ); return 0; } void visit(int i, int j) { int m, n; maze[i][j] = 1; if(i == endI && j == endJ) { printf("\n显示路径:\n"); for(m = 0; m <9; m++) { for(n = 0; n < 9; n++) if(maze[m][n] == 2) printf("█"); else if(maze[m][n] == 1) printf("◇"); else printf(" "); printf("\n"); } } if(maze[i][j+1] == 0) visit(i, j+1); if(maze[i+1][j] == 0) visit(i+1, j); if(maze[i][j-1] == 0) visit(i, j-1); if(maze[i-1][j] == 0) visit(i-1, j); maze[i][j] = 0; }

原文发布于微信公众号 - 数据库SQL(SQLdba)

原文发表时间:2015-05-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏冰霜之地

Threes-AI 玩小三传奇 (上)

1 个月前和另外二位小伙伴一起参加了一个 AI 的比赛。虽然比赛结果不理想,至少我享受到了编程过程中的乐趣。从这次比赛中让我认识到 Go 除了写服务端,写游戏模...

1282
来自专栏逸鹏说道

00.Web大前端时代之:HTML5+CSS3入门系列~Bug反馈文章

感谢广大网友的热心提醒,现已发现如下错误: 感谢 “ ”对画布笔记系列的反馈(QQ:350223285) ? 这个是失误,strokeStyle和stroke对...

2559
来自专栏吉浦迅科技

让NVIDIA Jetson AGX Xavier火力全开的秘密

之前我们写过让Jetson TX2火力全开的秘密,让大家知道命令行工具nvpmodel能够定义一组参数,从而有效地定义给定功率的性能。

2.1K3
来自专栏量子位

从零开始学习神经网络 | 视频教程

允中 发自 凹非寺 量子位 出品 | 公众号 QbitAI 爱好人工智能的你,一定想理解和创建神经网络吧,对不对? 好吧,我默认你是这么想的。呐,我们发现了一个...

3187
来自专栏我是攻城师

如何合理的控制solr查询的命中的数量和质量?

3865
来自专栏机器之心

资源 | 斯坦福大学发布Stanford.NLP.NET:集合多个NLP工具

选自斯坦福 机器之心编译 参与:李泽南、Smith 近日,斯坦福大学发布了 Stanford.NLP for .Net,为自然语言处理领域的开发者们提供帮助。顾...

3106
来自专栏小白课代表

有需求+小白课代表的软件目录(5.2)

1334
来自专栏云飞学编程

想知道python发展方向吗?来跟老师一起可视化拉勾网招聘信息吧!

772
来自专栏生信宝典

Graphpad,经典绘图工具初学初探

大多数科研文章都离不开图表,尤其是图,熟悉一些绘图软件,并将图在文章和PPT中展示出来,是科研训练的重要内容。漂亮的文章配图能给自己的工作加不少分,生信宝典推出...

1821
来自专栏coding

python使用PIL给图片添加文字生成海报

那时的我,对于未来有很多遐想:写小说、写时评、写诗歌... 总而言之,就是成为一个文字工作者

2142

扫码关注云+社区