【算法】老鼠走迷宫

老鼠走迷官(一)

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

相关文章

来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

32710
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3265
来自专栏魂祭心

原 canvas绘制clock

4294
来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

7218
来自专栏杨龙飞前端

scrollto 到指定位置

2564
来自专栏跟着阿笨一起玩NET

c#实现打印功能

2932
来自专栏菩提树下的杨过

Flash/Flex学习笔记(23):运动学原理

先写一个公用的小球类Ball: package{ import flash.display.Sprite; //小球 类 public class B...

25410
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2200
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5417
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2747

扫码关注云+社区