【算法】老鼠走迷宫

老鼠走迷官(一)

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

相关文章

来自专栏腾讯社交用户体验设计

效率至上—全新微云

1353
来自专栏GopherCoder

『简书API : jianshu 基于 golang (1)』

1534
来自专栏拂晓风起

cocos2d-js 和 createjs 性能对比(HTML5)

1144
来自专栏知晓程序

这款小程序,据说能识别(单身)狗

不过,我们一般都不知道自己遇到的是哪个品种。以至于跟别人描述的时候,只能手舞足蹈地比划它的样子,还很难说清楚。

712
来自专栏BestSDK

如何通过按键颜色的对比来引导用户

image.png 你有没有过意外点错按键的时候?当用户没有被正确引导时往往会在模态窗口上做出错误的决策。很多模态窗口会在不明确不同行动区别的条件下就弹出来。 ...

2247
来自专栏即时通讯技术

全面掌握移动端主流图片格式的特点、性能、调优等

图片通常是移动端应用流量耗费最多的部分,并且占据着重要的视觉空间。以大家最常用的即时通讯IM应用为例,应用中存在大量的图片数据往来(比如图片消息、用户相册、用户...

592
来自专栏华章科技

全球20个最佳大数据可视化工具,高级PPTers的法宝

Tableau 是一款企业级的大数据可视化工具。Tableau 可以让你轻松创建图形,表格和地图。 它不仅提供了PC桌面版,还提供了服务器解决方案,可以让您在...

914
来自专栏MixLab科技+设计实验室

全栈设计师技术Wiki之Polyfills

Polyfills 一项主要用于 web 前端开发的技术。 Polyfills 允许 Web 开发人员使用 HTML5 的 API ,而不管它是否受用户的浏览器...

34310
来自专栏FreeBuf

新式攻击使用W3C环境光线传感器来窃取浏览器的敏感信息

概述 在这篇文章中,我们将会给大家介绍一种从浏览器中提取敏感信息的方法,而我们所要用到的工具就是你的智能手机或笔记本电脑中的环境光传感器。文章结构如下: 1.首...

1665
来自专栏钱塘大数据

从入门到精通,全球20个最佳大数据可视化工具

数据可视化之初级篇 零编程工具 1. Tableau ? Tableau 是一款企业级的大数据可视化工具。Tableau 可以让你轻松创建图形,表格和地图。...

3294

扫描关注云+社区