程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> Java中棧.回溯.迷宮問題求解

Java中棧.回溯.迷宮問題求解

編輯：關於JAVA

考慮使用一個二維數組表示迷宮.所有的通路用0表示,牆用1表示,出口用9表示,入口用6表示,已經過點用3表示.輸出走出迷宮的過程.

從這個問題的求解過程中可以簡單總結出兩個算法,一是探路過程,二是輸出路線.

1.探路過程

探路過程算法可歸納為:

[1]從入口位置開始,檢查東西南北四個方向上的通路,如果發現出口則成功退出,否則將所有通路坐標壓入棧;

[2]從棧中取出一個坐標,將其標記為當前位置(標記數字3),再次判斷通路情況;

[3]如此進行,直到發現出口則成功退出,若棧空而且未發現出口,則失敗退出.

這裡使用到的回溯過程可描述為:

每到達一點時,會將所有可能的通路坐標(標記數字0的節點)壓入棧.所以當到達一點,而不存在可能的通路時,自然沒有相應的坐標壓入棧,而此時便從棧中取出上一個點所壓入的可能的一個通路坐標,並繼續作通路判斷,這便是一個回溯的過程.

2.輸出某一較短路線

將所有在探路過程中經過的點(標記數字3的節點)按實際探路路線存入隊列,對頭為入口, 隊尾為出口.這些點可能存在繞路的情況,所以可用下面的算法輸出某一較短路線.

[1]將隊尾(出口)節點設置為當前判斷節點;

[2]從當前判斷節點(x,y)的前驅節點開始,向前遍歷隊列,如果發現相鄰節點(其坐標可以為(x+1,y),(x-1,y),(x,y+1),(x,y-1)之一),則刪除該相臨節點至當前判斷節點的前驅節點之間的所有節點;

[3]將該相臨節點設置為當前判斷節點,繼續判斷相臨節點;

[4]當當前判斷節點為隊頭節點時退出.

該算法所得到的路線不一定是最短路線,想得到最短路線,可考慮使用樹結構將所有由出口至入口的路線保留為一子樹,樹高最短的子樹即為最短路線.但此算法可保證所得路線不會存在繞路情況.

3.表示節點坐標的類

public class MazeCell { 　　 private int x, y;//表示x軸y軸坐標　　 public MazeCell() { 　　 } 　　 public MazeCell(int i, int j) { 　　　　 x = i; 　　　　 y = j; 　　 } 　　 public boolean equals(Object o) { 　　　　 if (!(o instanceof MazeCell)) 　　　　　　 return false; 　　　　 MazeCell cell = (MazeCell) o; 　　　　 return cell.x == x && cell.y == y; 　　 } 　　 public String toString() { 　　　　 return x + "," + y; 　　 } 　　 public int getX() { 　　　　 return x; 　　 } 　　 public void setX(int x) { 　　　　 this.x = x; 　　 } 　　 public int getY() { 　　　　 return y; 　　 } 　　 public void setY(int y) { 　　　　 this.y = y; 　　 } }

4.所使用的棧數據結構

import java.util.LinkedList; public class Stack<T> { 　　 private LinkedList<T> storage = new LinkedList<T>(); 　　 /** 入棧 */ 　　 public void push(T v) { 　　　　 storage.addFirst(v); 　　 } 　　 /** 出棧，但不刪除 */ 　　 public T peek() { 　　　　 return storage.getFirst(); 　　 } 　　 /** 出棧 */ 　　 public T pop() { 　　　　 return storage.removeFirst(); 　　 } 　　 /** 棧是否為空 */ 　　 public boolean empty() { 　　　　 return storage.isEmpty(); 　　 } 　　 /** 打印棧元素 */ 　　 public String toString() { 　　　　 return storage.toString(); 　　 } }

5.求解迷宮問題

package net.zj.maze;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
public class Maze {
    private int rows = 0, cols = 0;// 迷宮的行數與列數
    private char[][] store, path;// 迷宮矩陣
    private MazeCell currentCell, exitCell = new MazeCell(),
            entryCell = new MazeCell();// 當前節點,出口節點,入口節點
    private static final char EXIT = '9', ENTRY = '6', VISITED = '3';// 出口標記,入口標記,已經過節點標記
    private static final char PASS = '0', WALL = '1';// 通路標記,牆標記
    private Stack<MazeCell> mazeStack = new Stack<MazeCell>();// 探路過程所使用棧
    private List<MazeCell> currentList = new LinkedList<MazeCell>();// 路經的路線隊列
    public Maze() {
        // 構造迷宮
        int row = 0, col = 0;
        Stack<String> mazeRows = new Stack<String>();
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader buffer = new BufferedReader(isr);
        System.out.println("Enter a rectangular maze using the following"
                + " characters: \n6-entry\n9-exit\n1-wall\n0-passage\n"
                + "Enter one line at a time; end with Ctrl-d;");
        try {
            String str = buffer.readLine();
            while (str != null) {
                row++;
                cols = str.length();
                str = "1" + str + "1";
                mazeRows.push(str);
                if (str.indexOf(EXIT) != -1) {
                    exitCell.setX(row);
                    exitCell.setY(str.indexOf(EXIT));
                }
                if (str.indexOf(ENTRY) != -1) {
                    entryCell.setX(row);
                    entryCell.setY(str.indexOf(ENTRY));
                }
                str = buffer.readLine();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        rows = row;
        store = new char[rows + 2][];
        store[0] = new char[cols + 2];
        for (; !mazeRows.empty(); row--)
            store[row] = (mazeRows.pop()).toCharArray();
        store[rows + 1] = new char[cols + 2];
        for (col = 0; col <= cols + 1; col++) {
            store[0][col] = WALL;
            store[rows + 1][col] = WALL;
        }
        path = new char[rows + 2][];
        copyArray(store, path);
    }
    /** 二維數組復制 */
    private void copyArray(char[][] src, char[][] tar) {
        for (int i = 0; i < src.length; i++) {
            tar[i] = new char[cols + 2];
            for (int j = 0; j < src[i].length; j++)
                tar[i][j] = src[i][j];
        }
    }
    /** 二維數組輸出 */
    private void display(PrintStream out, char[][] carray) {
        for (int row = 0; row <= rows + 1; row++)
            out.println(carray[row]);
        out.println();
    }
    /** 將未訪問並可通路的節點壓入棧 */
    private void pushUnvisited(int row, int col) {
        if (store[row][col] == PASS || store[row][col] == EXIT)
            mazeStack.push(new MazeCell(row, col));
    }
    /** 探路過程 */
    public void exitMaze(PrintStream out) {
        currentCell = entryCell;
        currentList.add(currentCell);
        out.println();
        while (!currentCell.equals(exitCell)) {
            int row = currentCell.getX();
            int col = currentCell.getY();
            display(System.out, store);
            if (!currentCell.equals(entryCell))
                store[row][col] = VISITED;
            pushUnvisited(row - 1, col);
            pushUnvisited(row + 1, col);
            pushUnvisited(row, col - 1);
            pushUnvisited(row, col + 1);
            if (mazeStack.empty()) {
                display(out, store);
                out.println("Failure");
                return;
            } else {
                currentCell = mazeStack.pop();
                currentList.add(currentCell);
            }
        }
        display(out, store);
        out.println("Success");
    }
    /** 得到某一輸出路線 */
    private void getPath() {
        if (currentList.size() <= 0)
            return;
        MazeCell cell = currentList.get(currentList.size() - 1);
        while (cell != currentList.get(0)) {
            List<MazeCell> subList = currentList.subList(0, currentList
                    .indexOf(cell));
            ListIterator<MazeCell> itr = subList.listIterator();
            while (itr.hasNext()) {
                MazeCell target = itr.next();
                if (adjoin(cell, target)) {
                    removeElements(currentList.indexOf(target) + 1, currentList
                            .indexOf(cell));
                    cell = target;
                    break;
                }
            }
        }
    }
    /** 刪除隊列中由from至to的連續元素 */
    private void removeElements(int from, int to) {
        int turn = to - from;
        while (turn > 0) {
            currentList.remove(from);
            turn--;
        }
    }
    /** 判斷兩個節點是否相鄰 */
    private boolean adjoin(MazeCell current, MazeCell target) {
        if ((current.getX() == target.getX() + 1 || current.getX() == target
                .getX() - 1)
                && (current.getY() == target.getY()))
            return true;
        if ((current.getY() == target.getY() + 1 || current.getY() == target
                .getY() - 1)
                && (current.getX() == target.getX()))
            return true;
        return false;
    }
    /** 輸出路線 */
    public void printPath(PrintStream out) {
        getPath();
        out.println("Path:");
        if (currentList.size() >= 2) {
            currentList.remove(currentList.size() - 1);
            currentList.remove(0);
        }
        Iterator<MazeCell> itr = currentList.iterator();
        while (itr.hasNext()) {
            MazeCell cell = itr.next();
            path[cell.getX()][cell.getY()] = VISITED;
        }
        display(System.out, path);
    }
    public static void main(String[] args) {
        Maze maze = new Maze();
        maze.exitMaze(System.out);
        maze.printPath(System.out);
    }
}

6.結果輸出

Enter a rectangular maze using the following characters: 6-entry 9-exit 1-wall 0-passage Enter one line at a time; end with Ctrl-d; 90000 11011 00000 00600 //構造的迷宮如下 1111111 1900001 1110111 1000001 1006001 1111111 //開始探路 1111111 1900001 1110111 1000001 1006001 1111111 1111111 1900001 1110111 1000001 1006301 1111111 1111111 1900001 1110111 1000001 1006331 1111111 1111111 1900001 1110111 1000031 1006331 1111111 1111111 1900001 1110111 1000331 1006331 1111111 1111111 1900001 1110111 1003331 1006331 1111111 1111111 1900001 1110111 1033331 1006331 1111111 1111111 1900001 1110111 1333331 1006331 1111111 1111111 1900001 1110111 1333331 1306331 1111111 1111111 1900001 1110111 1333331 1336331 1111111 //下一步為回溯過程 1111111 1900001 1110111 1333331 1336331 1111111 1111111 1900001 1113111 1333331 1336331 1111111 1111111 1903001 1113111 1333331 1336331 1111111 1111111 1903301 1113111 1333331 1336331 1111111 1111111 1903331 1113111 1333331 1336331 1111111 //下一步為回溯過程 1111111 1933331 1113111 1333331 1336331 1111111 Success Path: 1111111 1933001 1113111 1003001 1006001 1111111