递归算法的二维迷宫？ [英] Recursive Algorithm for 2D maze?

问题描述

（这不是一式两份）我们有一个二维迷宫的四侧包围X和有内在块了。
迷宫的这些特点都存储在二维数组。该方案必须找到，从开始的S为目标的G的路径。对于这一点，一个叫布尔值的方法解决（INT行，诠释列）的用途和用的行和列的索引初始化S。该算法必须是递归的。它应该返回true，如果它能够找到的路径，G和虚假其他明智的。以下是我试图解决这个问题，显示部分正确的结果。

(This is not a duplicate) We have a 2D maze surrounded by X on all 4 sides and there are inner blocks too.
All these characters of the maze is stored in 2D array. The program must find the path from start 'S' to goal 'G'. For this, a boolean method called 'solve(int row, int col) is uses and is initialized with row and column index of 'S'. The algorithm must be recursive. It should return true if its able to find the path to 'G' and false other wise. Here's how I tried to approach this problem which shows "partial correct result".

public boolean solve(int row, int col) {
  char right = this.theMaze[row][col + 1];
  char left = this.theMaze[row][col - 1];
  char up = this.theMaze[row - 1][col];
  char down = this.theMaze[row + 1][col];
  if (right == 'G' || left == 'G' || up == 'G' || down == 'G') {
    return true;
  }
  System.out.println("position=>"+"("+row + ":" + col+")");
  if (right == ' ') {
    return solve(row,col+1);
  }
  if (down == ' ') {
    return solve(row+1,col);
  }
  if (left == ' ') {
    return solve(row,col-1);
  }
  if (up == ' ') {
    return solve(row-1,col);
  }
  return false;
}

下面是它解决了输出：

   0 1 2 3 4 5 6 7 8 9 10 
0  X X X X X X X X X X X 
1  X X S X X X X X   X X 
2  X X   X X X X X   X X 
3  X X   X X X X X   X X 
4  X X   X X X X X   X X 
5  X X   X X X X X   X X 
6  X X   X X X X X   X X 
7  X X   X X X X X G X X 
8  X X               X X 
9  X X X X X X X X X X X 

position=>(1:2)
position=>(2:2)
position=>(3:2)
position=>(4:2)
position=>(5:2)
position=>(6:2)
position=>(7:2)
position=>(8:2)
position=>(8:3)
position=>(8:4)
position=>(8:5)
position=>(8:6)
position=>(8:7)
true

但是，当我把'G'一步拉（6,8）。它显示计算器错误。其原因是因为该递归2点之间发生在该状态下（以某种方式一样间接递归）。

But when I place 'G' one step up (at 6,8). It shows stackOverflow error. The reason is because the recursion occurs between 2 points at this state (somehow just like indirect recursion).

我怎样才能解决这个问题。反正是有告诉程序，而不是向上向下？改变的条件语句的位置，但不会工作。并认为有多个路径去，但只有一个会导致​​G的位置。如何回到初始位置，并尝试花药路径？先谢谢了。

How can I solve this problem. Is there anyway to tell the program to move up instead of down? Changing the position of conditional statements wont work though. And think a position that has more than one path to go but only one leads to 'G'. How to come back to initial position and try anther path ? Thanks in advance.

更新：

下面是这个问题由我一个解决方案。

推荐答案

您可以填补你已经通过加强空间的替代符号。所以，你的PROGRAMM就知道它在那里了。

You could fill in an alternate symbol in the spaces you stepped already through. So your programm will know that it was there already.

这篇关于递归算法的二维迷宫？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！