递归迷宫求解？

Question

可能重复：

Recursive Algorithm for 2D maze?

2d Maze from a text file?

Recursively Solving A Maze

所以我在一个文本文件阅读，这使得它成为一个二维数组，然后打印它出来了，起点是cha r S和结束点是F点，有效的移动只发生在虚线上，＃号是墙壁，试图找到一个递归方法来做到这一点，让我的方法开始叫做escape（），但是iono该怎么做该算法。

import java.io.BufferedReader; 
import java.io.FileInputStream; 
import java.io.FileNotFoundException; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Arrays; 

public class Maze 
{ 
    char[][] maze = new char[12][12]; 
    int startX, startY; 
    int endX, endY; 

    public Maze() throws IOException 
    { 
     create(); 
    } 

    public void create() throws IOException 
    { 
     FileInputStream in = new FileInputStream("maze.txt"); 
     BufferedReader br = new BufferedReader(new InputStreamReader(in)); 

     for(int j = 0; j<maze.length; j++) 
     { 
      maze[j] = br.readLine().replaceAll(" ", "").toCharArray(); 
     } 
     for(int i = 0; i<12; i++) 
     { 
      System.out.println(""); 
      for (int j = 0; j<12;j++) 
      { 
       System.out.print(maze[i][j]); 
      } 
     } 


     for(int i = 0; i<12; i++) 
     { 
      for (int j = 0; j<12; j++) 
      { 
       if(maze[i][j] == 'S') 
       { 
        startX = i; 
        startY = j; 
       } 
       if (maze [i][j] == 'F') 
       { 
        endX = i; 
        endY = j; 
       } 
      } 
     } 
     escape(startX, startY); 
    } 


    public boolean escape(int x, int y) 
    { 
     return true; 
    } 

} 

Answer 1

首先你需要一个基础条件。 “如果我们试图摆脱目标坐标，我们知道这是真的。”

public boolean escape(int x, int y) { 
    if(x == endx && y == endy) return true; 

    return false; 
} 

而且，如果我们试图从墙壁逃跑，这不是什么好：

public boolean escape(int x, int y) { 
    if(x == endx && y == endy) return true; 
    if(x < 0 || y < 0 || x > maze.length || y > maze[x].length) return false; 
    if(isWall(maze[x][y]) return false; // make isWall method 

    return false; 
} 

这是一个开始，但它不会帮助我们从开始到结束得到。那么我们如何尝试四面八方走（同时）

public boolean escape(int x, int y) { 
    if(x == endx && y == endy) return true; 
    if(x < 0 || y < 0 || x > maze.length || y > maze[x].length) return false; 
    if(isWall(maze[x][y]) return false; // make isWall method 

    return escape(x+1,y) || escape(x-1,y) || ecscape(x,y+1) || escape(x,y-1); 
} 

但是这也有问题。它会试图一次又一次从同一个方格中逃脱！所以我们必须将广场标记为已访问。让我们说''。未被访问，但'，'被访问。

public boolean escape(int x, int y) { 
    if(isVisited(x,y)) return false; // make isVisited method 
    if(x == endx && y == endy) return true; 
    if(x < 0 || y < 0 || x > maze.length || y > maze[x].length) return false; 
    if(isWall(maze[x][y]) return false; // make isWall method 


    return escape(x+1,y) || escape(x-1,y) || ecscape(x,y+1) || escape(x,y-1); 
} 

如果我们想知道，我们采取了方向，我们不得不这样做：

public boolean escape(int x, int y) { 
    if(isVisited(x,y)) return false; // make isVisited method 
    if(x == endx && y == endy) return true; 
    if(x < 0 || y < 0 || x > maze.length || y > maze[x].length) return false; 
    if(isWall(maze[x][y]) return false; // make isWall method 


    if(escape(x+1,y) || escape(x-1,y) || ecscape(x,y+1) || escape(x,y-1)) { 
     System.out.println(x + ", " + y); 
     return true; 
    } 
    return false; 
} 

Answer 2

递归地，最简单的算法是深度优先搜索。见http://en.wikipedia.org/wiki/Depth-first_search

本质的算法是一个二维图如下：

dfs(int x, int y) { 
    if (x, y) is the exit, return 0 
    if (x, y) is already visited or (x, y) is a wall, return infinity 
    mark the point (x, y) as visited in an array 
    return 1 + the minimum out of dfs(x+1, y), dfs(y+1, x), dfs(x-1, y), dfs(y-1, x) 
     // The output you return is part of the shortest path 
     // e.g. if dfs(x+1, y) is the smallest of the 4, then (x+1, y) is on the shortest path 
} 

这是最短路径问题，请参阅http://en.wikipedia.org/wiki/Shortest_path_problem约他们一些有用的信息。