`
chinagdvea
  • 浏览: 132382 次
  • 性别: Icon_minigender_1
  • 来自: 韶关
社区版块
存档分类
最新评论

用递归实现迷宫问题

J# 
阅读更多
1.编写迷宫类Maze.java

public class Maze {
  private final int PATH = 7; //PATH用于标记正确路径
  private final int TRIED = 3;//TRIED用于标记能通过且尝试过的路径

  private int[][] grid = {{1, 1, 0, 0},  1, 1, 1, 0}, {0, 1, 0, 0},
		        {0, 1, 1, 1}};  //构造一个迷宫,1表示可通过

  //穿越迷宫的递归方法,返回穿越迷宫成功与否的boolean值
  public boolean traverse(int row, int column) {
    boolean done = false;
    
    if (valid(row, column)) {
       grid[row][column] = TRIED;//标记为尝试过
        
        if (row = grid.length - 1 && column == grid[0].length - 1) {
         done = true;  //到达出口
        } else {
         done = traverse(row + 1, column);  //尝试向右走
        if (!done) {
          done = traverse(row, column + 1);  //尝试向下走;
         }
        if (!done) {
	 done = traverse(row - 1, column);  //尝试向左走
	}
        if (!done) {
	 done = traverse(row, column - 1);  //尝试向右走
        }
      }
      
      if (done) {
        grid[row][column] = PATH;
      }
    }

    return done;
  }

  //确定坐标能否通过
  public boolean valid(int row, int column) {
    boolean result = false;
    if (row < grid.length && column < grid[0].length) {
      if (grid[row][column] == 1) {
        result = true;
      }
    }
    return result;
  }

  public String toString() {
    String st = "";
    for (int i = 0; i < grid.length; i++) {
      for (int j = 0; j < grid[0].length; j++) {
        st += grid[i][j] + " ";
      }
      st += "\n";
    }
  }
}


2.编写测试类 TestMaze.java

public class TestMaze {
  public static void main(String[] args) {
    Maze maze = new Maze();
    System.out.println("The maze is:\n" + maze.toString());

    if (maze.traverse(0, 0)) {
      System.out.println("The maze has been passed:\n" + maze.toString());
    } else {
      System.out.println("The maze can't be passed!");
    }
  }
}
分享到:
评论

相关推荐

    Python基于递归算法实现的走迷宫问题

    在探讨如何使用Python实现走迷宫问题之前,我们先来了解一下递归算法的基本概念及其应用场景。 **递归**是一种非常重要的算法思想,在计算机科学中有着广泛的应用。简单来说,递归是指一个函数直接或间接地调用自身...

    用堆栈来实现递归的迷宫问题

    迷宫问题是典型的递归问题,递归问题一般可以用堆栈来实现,这个资源是描述迷宫问题的堆栈实现。

    C语言迷宫问题递归和非递归求解

    总的来说,C语言中的迷宫问题提供了一个实践数据结构和算法的好机会,无论选择递归还是非递归方法,都需要深入理解搜索策略和数据结构的运用。通过解决这类问题,可以提升编程思维和问题解决能力。

    用递归与非递归求解迷宫问题

    而如果对最短路径无特殊要求,且迷宫规模适中,DFS的递归实现可能更为直观。 在使用VC++6.0进行开发时,需要注意编译器对递归深度的限制,以及内存管理等问题。同时,理解并实现这两种方法对学习数据结构,尤其是...

    迷宫问题的非递归算法实现

    迷宫问题的非递归算法的实现,这是数据结构的经典算法,大家好好研究!

    C/C++:实现迷宫问题的最优解的递归算法.rar(含完整注释)

    本压缩包提供的"实现迷宫问题的最优解的递归算法"是一个利用递归方法来解决这类问题的例子。下面我们将详细探讨迷宫问题、递归算法以及如何用C/C++实现这一算法。 首先,迷宫问题可以抽象为一个图,其中每个节点...

    迷宫游戏C++数据结构递归算法实现

    本项目是用C++语言实现的迷宫游戏,重点在于利用数据结构和递归算法解决路径寻找问题。以下将详细讲解其中涉及的关键知识点。 首先,迷宫生成通常采用随机算法,比如深度优先搜索(DFS)或Prim算法。在这个项目中,...

    递归实现的迷宫

    用递归实现的迷宫,用二维数组表示迷宫,借助函数的递归栈,深度优先搜索

    链式栈实现递归和非递归迷宫路径求解

    本话题将深入探讨如何使用链式栈实现递归和非递归的迷宫路径求解方法,结合Java编程语言,以及深度优先搜索(DFS)策略。 首先,我们要理解链式栈是一种基于链表的数据结构,它支持栈的基本操作——压入(push)和...

    迷宫问题的非递归算法(栈实现.rar_迷宫 栈_迷宫 问题 非递归 算法_迷宫 非递归_迷宫问题_迷宫问题栈

    7. **资源辅助**:提供的压缩包文件中可能包含有关此算法的具体实现,如"迷宫问题的非递归算法(栈实现.txt)",可能是一个详细的算法描述或源代码示例。"www.pudn.com.txt"可能是相关资源的链接,供进一步学习和参考...

    递归和非递归解决迷宫问题

    (1)以链栈作为存储结构,编写一个求解迷宫的非递归程序,并将求得的通路以三元组(i,j,d)的形式输出,其中: i,j指示迷宫中的一个坐标,d表示走到下一坐标的方向; (2)编写递归形式的算法,求得迷宫中所有可能...

    递归解决迷宫问题

    数据结构中递归是一个重要的部分,此程序是回溯法实现了迷宫的问题,比较简单,亲自测试成功。

    数据结构C语言版__递归求解迷宫问题

    1. **迷宫表示**: 迷宫用二维数组`MazeType`表示,每个元素代表一个迷宫中的位置。数组中的值`0`表示墙壁(不可通行),`-1`表示通道(可通行)。 2. **递归算法**: 使用递归函数`Try`来尝试所有可能的路径,直到...

    迷宫问题之递归算法 绝对超值

    本程序利用递归策略,为解决迷宫问题提供了一种实用的解决方案。 首先,迷宫可以被抽象为一个二维网格,其中每个格子代表一个节点,节点之间通过连接线(通路)相互关联。迷宫有两个关键点:起点和终点,目标是从...

    函数递归走迷宫详解及代码

    本文将深入探讨如何使用函数递归解决这类问题,并通过创建迷宫程序来增强理解。递归是计算机科学中一种强大的工具,它允许函数调用自身以解决复杂问题。 首先,我们来理解"走迷宫"的算法。一个迷宫可以被抽象为一个...

    迷宫,用递归算法走迷宫。

    迷宫,用递归算法走迷宫,遇1回退,遇0前进。

    c#非递归求解迷宫最短路径-源码

    本项目“c#非递归求解迷宫最短路径-源码”是用C#编程语言实现的一个解决方案,它不依赖递归算法,而是采用其他策略寻找迷宫中的最短路径。以下是对这一主题的详细解释。 1. **迷宫问题概述**:迷宫问题通常被抽象为...

    迷宫用栈来实现迷宫问题。所用算法是非递归算法

    程序功能说明:本程序主要是用栈来实现迷宫问题。所用算法是非递归算法,输入为迷宫的行数和列数,然后在对应位置上输入其值(0表示该位置通,1表示该位置不通)。输出则是以三元组(i,j,d)的形式,其中(i,j)表示...

    用递归和非递归算法分别实现迷宫求解例子

    由0和1构成的m*n维矩阵M表示一个迷宫,其中0表示通路,1表示墙壁。迷宫入口为(1,1),出口为(m,n)。迷宫随机产生。试编一算法求出从入口点到出口点可沿八个方向或四个方向前进的一条通路,或显示没有通路

    迷宫的递归解法 源代码

    作者:西电软院 coder_jack@126.com 去我的...用google搜素关键字“风中之哨”排名第一的就是我的博客!够牛X吧!?学习严蔚敏的数据结构时老师布置的实践作业,采用递归解法求解迷宫中的通路。源码在VC6.0下编译通过!

Global site tag (gtag.js) - Google Analytics