【算法】老鼠走迷宫

老鼠走迷官(一)

说明老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用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 条评论
登录 后参与评论

相关文章

来自专栏机器之心

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

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

35460
来自专栏生信宝典

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

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

32810
来自专栏深度学习自然语言处理

详解中文维基百科数据处理流程及脚本代码

最近在做词向量相关工作,词向量的训练数据采用中文维基百科数据,训练之前,要对维基百科数据进行处理,这篇文章记录了一些处理过程及相关的脚本。

22920
来自专栏小白课代表

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

28730
来自专栏北京马哥教育

Python自然语言处理工具小结

作者:伏草惟存 来源:http://www.cnblogs.com/baiboy/p/nltk2.html 1 Python 的几个自然语言处理工具 NLTK:...

50770
来自专栏AI科技评论

开发 | 使用 Rodeo 分析总统候选人的推特内容

AI 科技评论按 :本文作者Datartisan,载于其知乎专栏——Datartisan数据工匠。AI 科技评论转载已获得原作者授权。 介绍 选举季已经到来,对...

389100
来自专栏云飞学编程

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

8720
来自专栏吉浦迅科技

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

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

3.9K30
来自专栏深度学习入门与实践

【原】Spark之机器学习(Python版)(二)——分类

  写这个系列是因为最近公司在搞技术分享,学习Spark,我的任务是讲PySpark的应用,因为我主要用Python,结合Spark,就讲PySpark了。然而...

27560
来自专栏冰霜之地

Threes-AI 玩小三传奇 (上)

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

18320

扫码关注云+社区

领取腾讯云代金券