再过两个月就要软考了,在准备的过程中,我发现算法是我的软肋,尤其是递归和回溯,一直不是很明白。最近在书上看了个题目,是迷宫问题。虽然我知道这种问题要采用回溯,反复试探,但具体到代码实现,就力不从心。于是认真阅读了C代码,自认为有点头绪了,就改成java重新实现一下。虽然大致结构没变,但通过自己写,感觉提高了不少。以下是代码:
public class Maze {
/*迷宫行数*/
public static final int M = 12;
/*迷宫列数*/
public static final int N = 15;
/*迷宫图,0代表通,1代表不通*/
/*最终解的路径上的元素置为8,曾经到达过,但无路可走而被迫回溯的元素置为4*/
public static int p[][]=
{
{0,1,0,0,0,1,1,0,0,0,1,1,1,1,1},
{1,0,0,0,1,1,0,1,1,1,0,0,1,1,1},
{0,1,1,0,0,0,0,1,1,1,1,0,0,1,1},
{1,1,0,1,1,1,1,0,1,1,0,1,1,0,0},
{1,1,0,1,1,1,1,0,1,1,0,1,1,0,0},
{1,1,0,1,0,0,1,0,1,1,1,1,1,1,1},
{0,0,1,1,0,1,1,1,0,1,0,0,1,1,1},
{0,1,1,1,1,0,0,1,1,1,1,1,1,1,1},
{0,0,1,1,0,1,1,0,1,1,1,1,1,0,1},
{1,1,0,0,0,1,1,0,1,1,0,0,0,0,0},
{0,0,1,1,1,1,1,0,0,0,1,1,1,1,0},
{0,1,0,0,1,1,1,1,1,0,1,1,1,1,0}
};
public static void maze(int p[][],int m,int n)
{
/*行前进方向:右、右下,下、左下、左、左上、上、右上*/
int is[] = {0,1,1,1,0,-1,-1,-1};
/*列前进方向:右、右下,下、左下、左、左上、上、右上*/
int js[] = {1,1,0,-1,-1,-1,0,1};
int stack[] = new int[3*M*N];
int top;
int i,j,v,g,h,jt = 0;
top = 0;
i =j = v = 0;
if(p[0][0]!=0)/*入口无路可走,提示无路,返回*/
{
p[0][0] = 4;
System.out.println("No Path!");
return;
}
while(top!=0||v!=7)/*只要没有退回到起点或者其余7个方向还有方向没走*/
{
/*选择一个方向*/
g = i+is[v];
h = j+js[v];
jt = 0;
if(g>-1&&g<m&&h>-1&&h<n)
{
/*已经到达了中点*/
if(g==m-1&&h ==n-1&&p[m-1][n-1]==0)
{
p[i][j] = 8;
p[g][h] = 8;
return; /*找到路径,返回*/
}
/*有通路*/
if(p[g][h]==0)
{
p[g][h] = 4;
p[i][j] = 8; /*前一步位置上置为8*/
/*入栈,记录下前一步*/
stack[top]=i;
stack[top+1]=j;
stack[top+2]=v;
top += 3;
i = g;
j = h;
v = 0;
jt = 1; /*标记为新发现的节点*/
}
}
if(jt == 0)
{
/*换个方向试试*/
if(v<7)
{
v++;
}
/*所有方向都试完了,开始回溯*/
else
{
/*如果上个结点也走投无路的,循环往上回退*/
while(top!=0 && stack[top-1]==7)
{
p[stack[top-3]][stack[top-2]]=4;/*无路,栈中元素置为4,并退栈*/
top-=3;
}
/*继续搜索上一个节点的其它方向*/
if(top!=0)
{
i = stack[top-3];
j = stack[top-2];
v = stack[top-1];
p[i][j] = 4;
top-=3;
}
}
}
}
System.out.println("No Path!");
return;
}
public static void main(String[] args) {
int i,j;
maze(p,12,15);
for(i = 0;i<M;i++)
{
for(j = 0;j<N;j++)
{
System.out.print(p[i][j]);
}
System.out.println();
}
}
}
分享到:
相关推荐
迷宫问题实验报告 迷宫问题是数据结构与算法实验报告的一部分,该实验的目的是熟悉栈的用法和掌握试探法程序设计技能。实验的内容是设计一个迷宫问题的解决方案,使用 C++ 语言编写程序来实现迷宫问题的解决。 ...
数据结构实验迷宫问题实验报告 本实验报告主要是关于数据结构实验中的迷宫问题,通过设计数据结构存储迷宫、设计存储结构保存从入口到出口的通路、设计算法完成迷宫问题的求解,并分析算法的时间复杂度。 首先,...
在计算机科学领域,迷宫问题是一个经典的问题,它涉及到路径搜索和图遍历算法。本文将深入探讨在C++环境中解决迷宫问题所涉及的知识点,包括基础的编程概念、数据结构以及算法。 首先,我们要了解C++语言基础。C++...
### 知识点一:迷宫问题背景及定义 在计算机科学中,迷宫问题是一种经典的搜索问题。题目描述了一个由0和1组成的m×n矩阵来表示迷宫,其中0表示可通行路径,1表示障碍物。目标是从迷宫的入口出发找到一条到达出口的...
### 数据结构程序设计-迷宫问题 #### 一、需求分析 迷宫问题是计算机科学领域内的一个典型问题,常用于教学和研究数据结构与算法。本项目旨在通过设计合适的数据结构和算法,解决一个给定的迷宫问题,即找出从迷宫...
数据结构栈和队列解决迷宫问题 本文档详细介绍了利用栈和队列解决迷宫问题的步骤,对于初学者学习数据结构能很好的进行辅导。本文档主要涉及到数据结构的两个重要概念:栈和队列,并介绍了如何使用这两个数据结构来...
《用栈解决迷宫问题的实验报告》 一、需求分析 在本次实验中,我们需要设计一个程序来解决迷宫问题。迷宫采用结构体Maze进行表示,其中包括以下关键属性: 1. pos:用于标记该位置是否存在障碍,通常用0表示通路,...
在本案例中,"回溯法解迷宫问题"是利用这种算法解决经典的迷宫寻路问题。 迷宫问题通常表现为一个二维矩阵,其中1表示墙壁,0表示可以通过的路径。目标是从起点(通常是迷宫的一个角落)到达终点,同时避开障碍物。...
迷宫问题(C语言源代码) 迷宫问题是计算机科学中的一种经典问题,旨在找到从迷宫入口到出口的路径。在这个问题中,我们使用C语言编写了一个迷宫问题的解决方案,该方案使用栈来实现迷宫的搜索。 问题描述 迷宫...
在给定的信息中,我们看到的是一个使用C语言实现的基于栈的数据结构来解决迷宫问题的示例。迷宫问题通常涉及到在一个二维网格中找到从起点到终点的有效路径,而这里的解决方案是通过广度优先搜索(BFS)或者深度优先...
### 数据结构与算法在迷宫问题中的应用 #### 背景介绍 迷宫问题是计算机科学领域中的一个经典问题,通常用于演示各种搜索算法的工作原理。在这个特定的问题中,我们面临的是一个M×N的矩阵,其中0表示通路而1则代表...
在IT领域,迷宫问题是一种经典的图论问题,它涉及到如何在一个二维网格中找到从起点到终点的最短路径。通常,我们可以通过多种算法来解决这个问题,其中之一就是使用队列的广度优先搜索(BFS)策略。在这个方法中,...
迷宫问题是一个经典的图论问题,常常用于计算机科学和算法设计的教学中。在这个问题中,我们通常有一个二维网格,其中的每个单元格要么是通路(通常标记为0),要么是障碍物(标记为1)。目标是找到从起点到终点的一...
在IT领域,迷宫问题是一种常见的算法挑战,它与数据结构紧密相关,特别是在设计和实现高效解决方案时。湖南大学可能在课程中涉及了这个主题,让学生深入理解数据结构的应用。迷宫问题通常要求找到从起点到终点的最短...
### C语言课程设计_迷宫问题 #### 一、项目背景与目标 本课程设计的主要目的是通过使用C语言实现一个迷宫求解器,旨在帮助学生深入理解C语言中的核心概念,如数组、函数、递归等,并通过解决实际问题的方式提高...
在IT领域,迷宫问题是一个经典的路径搜索问题,它经常被用来锻炼算法思维和编程技巧。迷宫可以被抽象为一个二维网格,其中每个单元格要么是通路(可通行),要么是墙壁(不可通行)。目标是找到从起点到终点的有效...
【数据结构迷宫问题实习作业】是一个典型的计算机科学问题,主要涉及到数据结构和算法的应用。在这个实习项目中,我们利用二维数组来表示一个m*n的迷宫,其中0表示可以通过的路径,1表示障碍物。目标是设计一个程序...
Java图形界面迷宫问题 Java图形界面迷宫问题是使用Java语言编写的图形用户界面程序,目的是解决迷宫问题。本节将详细介绍Java图形界面迷宫问题的实现原理、关键技术点和实际应用。 Java图形界面 Java图形界面是...
在计算机科学领域,迷宫问题是一个经典的路径搜索问题,它涉及到如何在给定的图形结构(通常是二维网格)中找到从起点到终点的最短路径。A*算法是一种高效的启发式搜索算法,广泛用于解决此类问题。本篇将详细介绍A*...