迷宫问题图文详解
- 作者: _老基哥
- 来源: 51数据库
- 2022-09-22
假设有一个 N*N 的正方形迷宫（如图 1 所示），老鼠必须从起始点移动到终点，它可以向上、向下、向左、向右移动，但仅限于在白色区域内移动。
图 1 N*N 迷宫
回溯算法可以很好地解决类似的迷宫问题，该算法能够从起点开始，逐一测试所有的移动路线，并最终找到能够达到终点的移动路线。
迷宫问题的解决方案
假设迷宫中可行走的白色区域用 1 表示， 不能行走的黑色区域用 0 表示，图 1 的迷宫可以用如下的矩阵表示：
1 0 1 1 1
1 1 1 0 1
1 0 0 1 1
1 0 0 1 0
1 0 0 1 1
这是一个 5*5 的矩阵，其中 (1,1) 为起点，(5,5) 为终点。
如下为回溯算法解决迷宫问题的伪代码：
输入 maze[ROW][COL] //输入迷宫地图，0 表示黑色区域，1 表示可行走区域
//(row,col) 表示起点，(outrow,outcol)表示终点
maze_puzzle(maze,row,col,outrow,outcol):
//回溯过程中，行走的每一区域都设为 Y，表示已经做了测试
maze[row][col] <- 'Y'
//如果行走至终点，表明有从起点到终点的路线
if row == outrow && col == outcol:
print maze // 输出行走路线
return
//测试从起点向上行走是否可行
if canMove(maze,row-1,col):
maze_puzzle(maze,row-1,col,outrow,outcol)
//测试从起点向左行走是否可行
if canMove(maze,row,col-1):
maze_puzzle(maze,row,col-1,outrow,outcol)
//测试从起点向下行走是否可行
if canmove(maze,row+1,col):
maze_puzzle(maze,row+1,col,outrow,outcol)
//测试从起点向右行走是否可行
if canmove(maze,row,col+1):
maze_puzzle(maze,row,col+1,outrow,outcol)
如下为解决图 1 迷宫问题的 C 语言程序：
#include <stdio.h>
typedef enum { false, true } bool;
#define ROW 5
#define COL 5
//假设当前迷宫中没有起点到终点的路线
bool find = false;
//回溯算法查找可行路线
void maze_puzzle(char maze[ROW][COL], int row, int col, int outrow, int outcol);
//判断指定路线是否可以行走
bool canMove(char maze[ROW][COL], int row, int col);
//输出行走路线
void printmaze(char maze[ROW][COL]);
int main()
{
char maze[ROW][COL] = {
{'1','0','1','1','1'},
{'1','1','1','0','1'},
{'1','0','0','1','1'},
{'1','0','0','1','0'},
{'1','0','0','1','1'} };
maze_puzzle(maze, 0, 0, ROW - 1, COL - 1);
if (find == false) {
printf("未找到可行线路");
}
return 0;
}
//(row,col) 表示起点，(outrow,outcol)表示终点
void maze_puzzle(char maze[ROW][COL], int row, int col, int outrow, int outcol) {
maze[row][col] = 'Y'; // 将各个走过的区域标记为 Y
//如果行走至终点，表明有从起点到终点的路线
if (row == outrow && col == outcol) {
find = true;
printf("成功走出迷宫,路线图为：\n");
printmaze(maze);
return ;
}
//尝试向上移动
if (canMove(maze, row - 1, col)) {
maze_puzzle(maze, row - 1, col, outrow, outcol);
//如果程序不结束，表明此路不通，恢复该区域的标记
maze[row - 1][col] = '1';
}
//尝试向左移动
if (canMove(maze, row, col - 1)) {
maze_puzzle(maze, row, col - 1, outrow, outcol);
//如果程序不结束，表明此路不通，恢复该区域的标记
maze[row][col - 1] = '1';
}
//尝试向下移动
if (canMove(maze, row + 1, col)) {
maze_puzzle(maze, row + 1, col, outrow, outcol);
//如果程序不结束，表明此路不通，恢复该区域的标记
maze[row + 1][col] = '1';
}
//尝试向右移动
if (canMove(maze, row, col + 1)) {
maze_puzzle(maze, row, col + 1, outrow, outcol);
//如果程序不结束，表明此路不通，恢复该区域的标记
maze[row][col + 1] = '1';
}
}
//判断指定路线是否可以行走
bool canMove(char maze[ROW][COL], int row, int col) {
//如果目标区域位于地图内，不是黑色区域，且尚未行走过，返回 true：反之，返回 false
return row >= 0 && row <= ROW - 1 && col >= 0 && col <= COL - 1 && maze[row][col] != '0' && maze[row][col] != 'Y';
}
//输出行走路线
void printmaze(char maze[ROW][COL]) {
int i, j;
for (i = 0;i < ROW; i++) {
for (j = 0; j < COL; j++) {
printf("%c ", maze[i][j]);
}
printf("\n");
}
}
如下为解决图 1 迷宫问题的 Java 程序：
public class Demo {
static boolean find = false;
static int ROW = 5;
static int COL = 5;
//(row,col) 表示起点，(outrow,outcol)表示终点
public static void maze_puzzle(char [][] maze, int row, int col, int outrow, int outcol) {
maze[row][col] = 'Y'; // 将各个走过的区域标记为 Y
//如果行走至终点，表明有从起点到终点的路线
if (row == outrow && col == outcol) {
find = true;
System.out.println("成功走出迷宫,路线图为：");
printmaze(maze);
return ;
}
//尝试向上移动
if (canMove(maze, row - 1, col)) {
maze_puzzle(maze, row - 1, col, outrow, outcol);
//如果程序不结束，表明此路不通，恢复该区域的标记
maze[row - 1][col] = '1';
}
//尝试向左移动
if (canMove(maze, row, col - 1)) {
maze_puzzle(maze, row, col - 1, outrow, outcol);
//如果程序不结束，表明此路不通，恢复该区域的标记
maze[row][col - 1] = '1';
}
//尝试向下移动
if (canMove(maze, row + 1, col)) {
maze_puzzle(maze, row + 1, col, outrow, outcol);
//如果程序不结束，表明此路不通，恢复该区域的标记
maze[row + 1][col] = '1';
}
//尝试向右移动
if (canMove(maze, row, col + 1)) {
maze_puzzle(maze, row, col + 1, outrow, outcol);
//如果程序不结束，表明此路不通，恢复该区域的标记
maze[row][col + 1] = '1';
}
}
//判断指定路线是否可以行走
public static boolean canMove(char [][] maze, int row, int col) {
//如果目标区域位于地图内，不是黑色区域，且尚未行走过，返回 true：反之，返回 false
return row >= 0 && row <= ROW - 1 && col >= 0 && col <= COL - 1 && maze[row][col] != '0' && maze[row][col] != 'Y';
}
//输出行走路线
public static void printmaze(char [][] maze) {
for(int i=0;i<ROW;i++) {
for(int j=0;j<COL;j++) {
System.out.print(maze[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
char [][]maze = new char[][]{
{'1','0','1','1','1'},
{'1','1','1','0','1'},
{'1','0','0','1','1'},
{'1','0','0','1','0'},
{'1','0','0','1','1'} };
maze_puzzle(maze, 0, 0, ROW - 1, COL - 1);
if (find == false) {
System.out.print("未找到可行线路");
}
}
}
如下为解决图 1 迷宫问题的 Python 程序：
#指定地图的行数和列数
ROW = 5
COL = 5
#初始化地图
maze =[['1','0','1','1','1'],
['1','1','1','0','1'],
['1','0','0','1','1'],
['1','0','0','1','0'],
['1','0','0','1','1']]
#假设当前迷宫中没有起点到终点的路线
find = False
#回溯算法查找可行路线
def maze_puzzle(maze,row,col,outrow,outcol):
global find
maze[row][col] = 'Y'
if row == outrow and col == outcol:
find = True
print("成功走出迷宫,路线图为：")
printmaze(maze)
return
if canMove(maze,row-1,col):
maze_puzzle(maze, row - 1, col, outrow, outcol)
#如果程序不结束，表明此路不通，恢复该区域的标记
maze[row - 1][col] = '1'
if canMove(maze, row, col - 1):
maze_puzzle(maze, row, col - 1, outrow, outcol)
#如果程序不结束，表明此路不通，恢复该区域的标记
maze[row][col - 1] = '1'
#尝试向下移动
if canMove(maze, row + 1, col):
maze_puzzle(maze, row + 1, col, outrow, outcol)
#如果程序不结束，表明此路不通，恢复该区域的标记
maze[row + 1][col] = '1'
#尝试向右移动
if canMove(maze, row, col + 1):
maze_puzzle(maze, row, col + 1, outrow, outcol)
#如果程序不结束，表明此路不通，恢复该区域的标记
maze[row][col + 1] = '1'
#判断指定路线是否可以行走
def canMove(maze,row,col):
return row >= 0 and row <= ROW - 1 and col >= 0 and col <= COL - 1 and maze[row][col] != '0' and maze[row][col] != 'Y'
#输出行走路线
def printmaze(maze):
for i in range(0,ROW):
for j in range(0,COL):
print(maze[i][j],end=" ")
print()
maze_puzzle(maze,0,0,ROW-1,COL-1)
if find == False:
print("未找到可行路线")
以上程序的输出结果均为：
成功走出迷宫,路线图为：
Y 0 Y Y Y
Y Y Y 0 Y
1 0 0 Y Y
1 0 0 Y 0
1 0 0 Y Y
其中，'Y' 表示可行的移动路线。
推荐阅读
热点文章
检查拆分键盘
0
带有“上一个"的工具栏和“下一个"用于键盘输入AccessoryView
0
Activity 启动时显示软键盘
0
UIWebView 键盘 - 摆脱“上一个/下一个/完成"酒吧
0
在 iOS7 中边缘滑动时，使键盘与 UIView 同步动画
0
我的 iOS 应用程序中的键盘在 iPhone 6 上太高了.如何在 XCode 中调整键盘的分辨率?
0
android:inputType="textEmailAddress";- '@' 键和 '.com' 键?
0
禁用 iPhone 中键盘的方向
0
Android 2.3 模拟器上的印地语键盘问题
0
keyDown 没有被调用
0
