大家好，欢迎来到IT知识分享网。
经典算法大全51例——5&6.老鼠走迷官
算法目录合集
地址
算法目录合集
说明
该地址指向所有由本人自己所经历的算法习题(也有可能仅仅是一个入门的案例或者是经典案例)，仅仅为我做过而且比较有意思的，也许还会有一些我自己想出来的，出于兴趣写在这里,具体格式我会在下面列明，总目录也会在这里出现，方便查阅以及自己进行复习回顾。
题目以及个人题解
说明
这个在原文中是两个题,我把他们综合一下，作为一个题展现给大家，为了不水贴嘛，看看我有多好啊🤗🤗🤗🤗哈哈哈。
题目
{ {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}}
特别说明
第二个问题（思考部分）其实在《经典算法大全51例》里面是第六道题，我看类型太过相似了，简直就是一道题，所以我合在一起了
原理分析
其实很简单，就像第一句怼我的话：哪儿有路往哪儿走，那么在程序中怎么让老鼠拥有眼睛呢？那很简单，假如现在老鼠随便站一个位置（这个位置肯定是0啊，别跟我犟，哼哼😕），那么我们就去看看这个位置的上下左右是不是可以通行（0是空地，2是墙壁），如果是0，那么就可以让老鼠到这儿，并且再次进行是否可以通行的判断，那么问题来了，万一这只老鼠反复横跳😕怎么办?就像这种矩阵：
其实避免这种情况的方法题目里也已经给我们了：使用1来表示老鼠的行走路径。那么我们只需要判断周围是不是0就可以了，这样就可以在最后显示出来路径了。
问题①
原理
我们先来做第一问：只寻找一条路：
为了方便展示，我们先画出来地图原图来把矩阵进行展示，然后调用老鼠行走的方法，最后绘制带有路径的地图，这就是主方法：
//打印地图 for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路 case 0: System.out.print(" "); break; //代表墙 case 2: System.out.print("📦"); break; default: break; } } System.out.println(); } //开始寻找 seekOnce(maze, startRow, startRank); System.out.println("====================="); //打印路径 if (success) {
for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路 case 0: System.out.print(" "); break; //代表老鼠走的路 case 1: System.out.print("🐾"); break; //代表墙 case 2: System.out.print("📦"); break; default: break; } } System.out.println(); } } else {
System.out.println("找不到出口"); } } 而对于老鼠行走的方法，我们在原理分析的时候已经分析过了，首先把老鼠走过的位置从0变成1（🐶：“这是不是和我撒尿一个道理？”，🙄：“我呸！”），然后继续找上下左右哪里有0，有0就过去，把他变成1（🎃感觉怪怪的？？🎃）：
maze[i][j] = 1; if (!success && maze[i][j + 1] == 0) {
seekOnce(maze, i, j + 1); } if (!success && maze[i + 1][j] == 0) {
seekOnce(maze, i + 1, j); } if (!success && maze[i][j - 1] == 0) {
seekOnce(maze, i, j - 1); } if (!success && maze[i - 1][j] == 0) {
seekOnce(maze, i - 1, j); } 没0就不用继续讨论了；假如某条分支A，调用了四个方向，发现四周不是走过的路（1）就是墙（2），那么就再把这条分支变回0就行了：
if (!success) {
maze[i][j] = 0; } 一直等老鼠到达了我们指定的终点，那么就把标识是否完成迷宫的标识符变成true，那么就成功了，如果遍历完了所有格子，我们的小老鼠依旧没有到达指定的重点，那么标识符还是false，最后我们只需要将标识符返回，就可以判断是否有这么一条路径可以让老鼠达到终点了：
if (success) {
//打印地图 } else {
System.out.println("找不到出口"); } 可以注意一下，因为结束的条件有两种，一个是找完所有的路，然后发现没有出口，结束了整个流程，另一种就是已经找到了重点，那这个时候何必继续调用方法呢，所以每一条我都增加了判断条件：
if (success) 代码实现——Java
package com.interest; / * com.interest * * @author g55zhw * @create 2020-09-30-20-54 */ public class MouseFindOnce {
static int startRow = 1, startRank = 1; static int endRow = 7, endRank = 7; static int count = 1; static boolean success = false; static int[][] maze = new int[][]{
{
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} }; public static void main(String[] args) {
//打印地图 for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路 case 0: System.out.print(" "); break; //代表墙 case 2: System.out.print("📦"); break; default: break; } } System.out.println(); } //开始寻找 seekOnce(maze, startRow, startRank); System.out.println("====================="); //打印路径 if (success) {
for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路 case 0: System.out.print(" "); break; //代表老鼠走的路 case 1: System.out.print("🐾"); break; //代表墙 case 2: System.out.print("📦"); break; default: break; } } System.out.println(); } } else {
System.out.println("找不到出口"); } } static boolean seekOnce(int[][] maze, int i, int j) {
System.out.println("(" + i + "," + j + ")" + count); count++; maze[i][j] = 1; if (i == endRow && j == endRank) {
success = true; } if (!success && maze[i][j + 1] == 0) {
seekOnce(maze, i, j + 1); } if (!success && maze[i + 1][j] == 0) {
seekOnce(maze, i + 1, j); } if (!success && maze[i][j - 1] == 0) {
seekOnce(maze, i, j - 1); } if (!success && maze[i - 1][j] == 0) {
seekOnce(maze, i - 1, j); } if (!success) {
maze[i][j] = 0; } return success; } } 📦📦📦📦📦📦📦📦📦 📦 📦 📦 📦📦 📦📦 📦 📦 📦 📦 📦 📦 📦 📦 📦 📦 📦 📦 📦 📦📦 📦📦 📦📦📦 📦 📦 📦📦📦📦📦📦📦📦📦 (1,1)1 (1,2)2 (1,3)3 (1,4)4 (1,5)5 (1,6)6 (1,7)7 (2,7)8 (3,7)9 (4,7)10 (5,7)11 (3,6)12 (2,4)13 (3,4)14 (3,3)15 (4,3)16 (5,3)17 (5,4)18 (5,5)19 (6,5)20 (7,5)21 (7,6)22 (7,7)23 📦📦📦📦📦📦📦📦📦 📦🐾🐾🐾🐾 📦 📦 📦📦🐾📦📦 📦 📦 📦🐾🐾📦 📦 📦 📦🐾📦 📦 📦 📦 🐾🐾🐾📦 📦 📦📦 📦📦🐾📦📦📦 📦 🐾🐾🐾📦 📦📦📦📦📦📦📦📦📦 大家可以看到，除了打印了地图我还增加了一条打印内容，那就是现在进行的地点以及第几次调用方法，大家把上下左右的顺序换一换，这个值也会发生变化，比如先判断向下走：
if (!success && maze[i + 1][j] == 0) {
seekOnce(maze, i + 1, j); } if (!success && maze[i][j + 1] == 0) {
seekOnce(maze, i, j + 1); } if (!success && maze[i - 1][j] == 0) {
seekOnce(maze, i - 1, j); } if (!success && maze[i][j - 1] == 0) {
seekOnce(maze, i, j - 1); } 这样的话，那路线就是向下为主了，大家可以自己试一试。
问题②
原理
第二个问题其实经过了第一题的洗礼，大家应该很容易就接受了，我就不一步一步说步骤了，说一个大致的过程，然后在代码里放一串“神秘代码”，大家自然就可以理解了：
①首先把成功标识符去掉，这样才能让老鼠就算成功到达了一次重点也不至于终结整个方法；
重要：
②（这段解释同样实用于问题一，但是在这里更容易理解，我才放在这儿了）我增加了这么一条语句来帮助大家理解，其实并不是老鼠在走，走到终点或者走不动了才回头，而是我们认为地去调方法，因为如果真的是老鼠在走，那么就不会一下子执行100多次才会终止了，真正的情况是：我们每次调用方法的时候，都是相当于施行了一次“影分身”，假如老鼠站的位置现在上左不能走，那么我们就让他去下和右，这样就分了一次身；去右边那个假如又遇到分叉了，再分身……剩下的就是和问题一的执行类似了，有路到终点，那么1就是1，0就是0，如果这个分支到不了终点，那么0还是0，1也是0；
System.out.println("========第" + count + "次调用seekForever方法========"); count++; 代码实现——Java
package com.interest; / * com.interest * * @author g55zhw * @create 2020-09-30-21-14 */ public class MouseFindAll {
static int startRow = 1, startRank = 1; static int endRow = 7, endRank = 7; static int count = 1; static int[][] mazeTitle = new int[][]{
{
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} }; public static void main(String[] args) {
seekForever(mazeTitle, startRow, startRank); } static void seekForever(int[][] maze, int i, int j) {
//首先赋值为1,表示这块地板我已经来了 maze[i][j] = 1; System.out.println("========第" + count + "次调用seekForever方法========"); count++; //打印地图 if (i == endRow && j == endRank) {
for (int m = 0; m < maze.length; m++) {
for (int n = 0; n < maze[m].length; n++) {
switch (maze[m][n]) {
//代表路 case 0: System.out.print(" "); break; //代表老鼠走的路 case 1: System.out.print("🐾"); break; //代表墙 case 2: System.out.print("📦"); break; default: break; } } System.out.println(); } }else {
System.out.println("还没有到终点"); } //以下四个方向,有任何一个方向是路(0)的话,就可以通行(调用seekForever方法); if (maze[i][j + 1] == 0) {
seekForever(maze, i, j + 1); } if (maze[i + 1][j] == 0) {
seekForever(maze, i + 1, j); } if (maze[i - 1][j] == 0) {
seekForever(maze, i - 1, j); } if (maze[i][j - 1] == 0) {
seekForever(maze, i, j - 1); } //四个方向都没有路的话就把已经踩过的地板换回0,假装没来过→_→ maze[i][j] = 0; } } 结果演示
========第1次调用seekForever方法======== 还没有到终点 ========第2次调用seekForever方法======== 还没有到终点 ========第3次调用seekForever方法======== 还没有到终点 ========第4次调用seekForever方法======== 还没有到终点 ========第5次调用seekForever方法======== 还没有到终点 ========第6次调用seekForever方法======== 还没有到终点 ========第7次调用seekForever方法======== 还没有到终点 ========第8次调用seekForever方法======== 还没有到终点 ========第9次调用seekForever方法======== 还没有到终点 ========第10次调用seekForever方法======== 还没有到终点 ========第11次调用seekForever方法======== 还没有到终点 ========第12次调用seekForever方法======== 还没有到终点 ========第13次调用seekForever方法======== 还没有到终点 ========第14次调用seekForever方法======== 还没有到终点 ========第15次调用seekForever方法======== 还没有到终点 ========第16次调用seekForever方法======== 还没有到终点 ========第17次调用seekForever方法======== 还没有到终点 ========第18次调用seekForever方法======== 还没有到终点 ========第19次调用seekForever方法======== 还没有到终点 ========第20次调用seekForever方法======== 还没有到终点 ========第21次调用seekForever方法======== 还没有到终点 ========第22次调用seekForever方法======== 还没有到终点 ========第23次调用seekForever方法======== 📦📦📦📦📦📦📦📦📦 📦🐾🐾🐾🐾 📦 📦 📦📦🐾📦📦 📦 📦 📦🐾🐾📦 📦 📦 📦🐾📦 📦 📦 📦 🐾🐾🐾📦 📦 📦📦 📦📦🐾📦📦📦 📦 🐾🐾🐾📦 📦📦📦📦📦📦📦📦📦 ========第24次调用seekForever方法======== 还没有到终点 ========第25次调用seekForever方法======== 还没有到终点 ========第26次调用seekForever方法======== 还没有到终点 ========第27次调用seekForever方法======== 还没有到终点 ========第28次调用seekForever方法======== 还没有到终点 ========第29次调用seekForever方法======== 还没有到终点 ========第30次调用seekForever方法======== 还没有到终点 ========第31次调用seekForever方法======== 还没有到终点 ========第32次调用seekForever方法======== 还没有到终点 ========第33次调用seekForever方法======== 还没有到终点 ========第34次调用seekForever方法======== 还没有到终点 ========第35次调用seekForever方法======== 还没有到终点 ========第36次调用seekForever方法======== 还没有到终点 ========第37次调用seekForever方法======== 还没有到终点 ========第38次调用seekForever方法======== 还没有到终点 ========第39次调用seekForever方法======== 还没有到终点 ========第40次调用seekForever方法======== 还没有到终点 ========第41次调用seekForever方法======== 还没有到终点 ========第42次调用seekForever方法======== 📦📦📦📦📦📦📦📦📦 📦🐾🐾🐾🐾 📦 📦 📦📦🐾📦📦 📦 📦 📦🐾🐾📦 📦 📦 📦🐾📦 📦 📦 📦 🐾🐾 📦 📦 📦📦🐾📦📦 📦📦📦 📦 🐾🐾🐾🐾🐾🐾📦 📦📦📦📦📦📦📦📦📦 ========第43次调用seekForever方法======== 还没有到终点 ========第44次调用seekForever方法======== 还没有到终点 ========第45次调用seekForever方法======== 还没有到终点 ========第46次调用seekForever方法======== 还没有到终点 ========第47次调用seekForever方法======== 还没有到终点 ========第48次调用seekForever方法======== 还没有到终点 ========第49次调用seekForever方法======== 还没有到终点 ========第50次调用seekForever方法======== 还没有到终点 ========第51次调用seekForever方法======== 还没有到终点 ========第52次调用seekForever方法======== 还没有到终点 ========第53次调用seekForever方法======== 还没有到终点 ========第54次调用seekForever方法======== 还没有到终点 ========第55次调用seekForever方法======== 还没有到终点 ========第56次调用seekForever方法======== 还没有到终点 ========第57次调用seekForever方法======== 还没有到终点 ========第58次调用seekForever方法======== 还没有到终点 ========第59次调用seekForever方法======== 还没有到终点 ========第60次调用seekForever方法======== 还没有到终点 ========第61次调用seekForever方法======== 还没有到终点 ========第62次调用seekForever方法======== 还没有到终点 ========第63次调用seekForever方法======== 📦📦📦📦📦📦📦📦📦 📦🐾 📦 📦🐾📦📦 📦📦 📦 📦🐾📦 📦 📦 📦🐾📦 📦 📦 📦 📦🐾🐾🐾🐾🐾📦 📦 📦📦 📦📦🐾📦📦📦 📦 🐾🐾🐾📦 📦📦📦📦📦📦📦📦📦 ========第64次调用seekForever方法======== 还没有到终点 ========第65次调用seekForever方法======== 还没有到终点 ========第66次调用seekForever方法======== 还没有到终点 ========第67次调用seekForever方法======== 还没有到终点 ========第68次调用seekForever方法======== 还没有到终点 ========第69次调用seekForever方法======== 还没有到终点 ========第70次调用seekForever方法======== 还没有到终点 ========第71次调用seekForever方法======== 还没有到终点 ========第72次调用seekForever方法======== 还没有到终点 ========第73次调用seekForever方法======== 还没有到终点 ========第74次调用seekForever方法======== 还没有到终点 ========第75次调用seekForever方法======== 还没有到终点 ========第76次调用seekForever方法======== 还没有到终点 ========第77次调用seekForever方法======== 还没有到终点 ========第78次调用seekForever方法======== 还没有到终点 ========第79次调用seekForever方法======== 还没有到终点 ========第80次调用seekForever方法======== 还没有到终点 ========第81次调用seekForever方法======== 还没有到终点 ========第82次调用seekForever方法======== 还没有到终点 ========第83次调用seekForever方法======== 还没有到终点 ========第84次调用seekForever方法======== 还没有到终点 ========第85次调用seekForever方法======== 还没有到终点 ========第86次调用seekForever方法======== 还没有到终点 ========第87次调用seekForever方法======== 还没有到终点 ========第88次调用seekForever方法======== 还没有到终点 ========第89次调用seekForever方法======== 还没有到终点 ========第90次调用seekForever方法======== 还没有到终点 ========第91次调用seekForever方法======== 📦📦📦📦📦📦📦📦📦 📦🐾 📦 📦🐾📦📦 📦📦 📦 📦🐾📦 📦 📦 📦🐾📦 📦 📦 📦 📦🐾🐾 📦 📦 📦📦🐾📦📦 📦📦📦 📦 🐾🐾🐾🐾🐾🐾📦 📦📦📦📦📦📦📦📦📦 ========第92次调用seekForever方法======== 还没有到终点 ========第93次调用seekForever方法======== 还没有到终点 ========第94次调用seekForever方法======== 还没有到终点 ========第95次调用seekForever方法======== 还没有到终点 ========第96次调用seekForever方法======== 还没有到终点 ========第97次调用seekForever方法======== 还没有到终点 ========第98次调用seekForever方法======== 还没有到终点 ========第99次调用seekForever方法======== 还没有到终点 ========第100次调用seekForever方法======== 还没有到终点 ========第101次调用seekForever方法======== 还没有到终点 ========第102次调用seekForever方法======== 还没有到终点 ========第103次调用seekForever方法======== 还没有到终点 ========第104次调用seekForever方法======== 还没有到终点 ========第105次调用seekForever方法======== 还没有到终点 ========第106次调用seekForever方法======== 还没有到终点 ========第107次调用seekForever方法======== 还没有到终点 ========第108次调用seekForever方法======== 还没有到终点 ========第109次调用seekForever方法======== 还没有到终点 ========第110次调用seekForever方法======== 还没有到终点 ========第111次调用seekForever方法======== 还没有到终点 ========第112次调用seekForever方法======== 还没有到终点 相关题目其他变形：
1.地下城游戏（来源：力扣LeetCode）
其他的变形我也不给了，十一了，明天就要出去浪了，懒得自己想了🙄🙄，哈哈哈，其实相关类似的题在力扣领扣都挺多的，大家可以自己去看看，很好玩儿的。
官方题解
老鼠走迷宫（一）
解法
老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止，这是递回的基本题，请直接看程式应就可以理解。
代码——C语言
#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; } 老鼠走迷宫（二）
解法
求所有路径看起来复杂但其实更简单，只要在老鼠走至出口时显示经过的路径，然后退回上一格重新选择下一个位置继续递回就可以了，比求出单一路径还简单，我们的程式只要作一点修改就可以了。
代码——C语言
#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; } 免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/107777.html
