【算法】老鼠走迷宫

老鼠走迷官(一)

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

相关文章

来自专栏IT派

你以为越复杂的密码越安全?小心那些错误认知

如何在网络社会中保护自己的个人隐私,长久以来都是一个让人挥之不去的现实问题。几十年的积累,现代人已经完全掌握了密码的“构造”方法,自认为从此便可以真的高枕无忧,...

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

QQfamily减肥篇来啦!- 腾讯ISUX

1353
来自专栏机器之心

资源 | 基于Python的开源人脸识别库:离线识别率高达99.38%

选自Github 机器之心编译 参与:路雪 仅用 Python 和命令行就可以实现人脸识别的库开源了。该库使用 dlib 顶尖的深度学习人脸识别技术构建,在户外...

3858
来自专栏数据科学与人工智能

【陆勤践行】小白一天之内玩转机器学习!

很多朋友都对机器学习心存各种敬畏之心。实际上,机器学习更多的也不过是我们“统计学习”的扩展延伸和行业实现的具体化。无非是通过样本数据发现规律性的东西而已。何况“...

1755
来自专栏ATYUN订阅号

适用于Windows 10的深度学习环境设置

本文详细介绍如何开始深度学习,首先在Windows 10上配置适合它的环境。要安装的框架是Keras API,后端为TensorFlow的GPU版本。

753
来自专栏编程

用在线RaxML构建系统发育树

本文将以在线的RAxML为例进行讲解: 测试数据及结果和相关处理软件已经上传至百度网盘:http://pan.baidu.com/s/1i5cPyXB密码:b2...

2157
来自专栏吉浦迅科技

当Intel的神经棒遇到NVIDIA的Jetson TX2

3215
来自专栏AI2ML人工智能to机器学习

强化学习体验之小游戏 FlappyBird

在安装完TensorFlow之后(详见” Install TensorFlow in Ubuntu 16.04.1 LTS “), 就可以测试各种深度学习的算法...

601
来自专栏Y大宽

多序列比对,进化树分析,保守性,密码子偏好性分(1)

打开https://www.ncbi.nlm.nih.gov/protein,输入BopA,search

992
来自专栏小文博客

种子、磁力链、番号你真的了解吗?

1.5K6

扫码关注云+社区