栈与回溯:迷宫问题

  迷宫问题是栈的典型应用,栈通常也与回溯算法连用。 回溯算法的基本描述是:

  (1)  选择一个起始点;

(2)  如果已达目的地, 则跳转到 (4); 如果没有到达目的地, 则跳转到 (3) ;

  (3)  求出当前的可选项;

a.  若有多个可选项,则通过某种策略选择一个选项,行进到下一个位置,然后跳转到 (2);

b.  若行进到某一个位置发现没有选项时,就回退到上一个位置,然后回退到 (2) ;

(4) 退出算法。

在回溯算法的实现中,通常要使用栈来保存行进中的位置及选项。本文给出自己写的迷宫回溯算法实现及简要说明。

  1.  首先给出栈的抽象数据结构 StackADT<T> : 主要是入栈、出栈、判断空、长度、展示操作;

package zzz.study.javagui.maze;

public interface StackADT<T> {

    /* 判断是否为空栈;若为空,返回TRUE, 否则返回FALSE */
    public boolean isEmpty();

    /* 入栈操作: 将元素 e 压入栈中    */
    public void push(T e);

    /* 出栈操作: 若栈非空,将栈顶元素弹出并返回;若栈空,则抛出异常  */
    public T pop();

    /* 返回栈顶元素,但并不将其弹出  */
    public T peek();

    /* 返回栈长度,即栈中元素的数目 */
    public int size();

    /* 遍历操作: 若栈非空,遍历栈中所有元素  */
    public String toString();

}

  2.  可变长的栈的实现 DyStack<T>: 借助 ArrayList 及一个指针来实现。注意到这里使用泛型来保证栈的通用性。

package zzz.study.javagui.maze;

import java.util.ArrayList;

public class DyStack<T> implements StackADT<T> {

    private final int INIT_STACK_SIZE = 20;

    ArrayList<T> ds;        // 栈元素列表
    private int top;       // 栈顶索引:当前栈顶元素的下一个元素的索引

    /*
     * 构造器:
     * 使用默认容量创建一个空栈
     *
     */
    public DyStack() {
        top = 0;
        ds = new ArrayList<T>(INIT_STACK_SIZE);
    }

    /*
     * 构造器:
     * 使用指定容量创建一个空栈
     *
     */
    public DyStack(int capacity) {

        top = 0;
        ds = new ArrayList<T>(capacity);
    }

    public boolean isEmpty() {

        if (top == 0)
            return true;
        else
            return false;
    }

    public void clear() {
        top = 0;
        ds.clear();
    }

    public void push(T e) {

        ds.add(top, e);
        top++;
    }

    public T pop() {

        if (ds.isEmpty())
            throw new StackEmptyException("The stack has been empty!");
        top--;
        T result = ds.get(top);
        ds.set(top, null);
        return result;
    }

    public T peek() {

        if (ds.isEmpty())
            return null;
        return ds.get(top - 1);
    }

    public int size() {
        return top;
    }

    public String toString() {

        StringBuilder content = new StringBuilder(" ");
        for (int i = 0; i < top; i++) {
            content.append(" --> ");
            content.append(ds.get(i));
        }
        return content.toString();
    }

    public int getTop() {
        return top;
    }

}

class StackEmptyException extends RuntimeException {

    public StackEmptyException(String msg) {
        super(msg);
    }
}

3.  迷宫位置的数据结构 Position: 这里为了"节约内存"方向选择了 byte 类型,实际上在小型程序里是不必要的,带来了繁琐的类型转换,也带来了一些隐藏的问题。比如 Set<Byte> dirs 包含 byte 1;  但 dirs.contains(1) 会返回 false , 而 dirs.contains((byte)1) 才会返回 true.  Position 要在集合中使用,最好实现 equals 和 hashCode 方法。注意 equals 不要写成了 equal,  hashCode 不要写成 hashcode , 这些我都犯过错的 :)

package zzz.study.javagui.maze;

/*
 *  迷宫中的通道位置模型:
 *  row: 所处位置的行坐标
 *  col: 所处位置的列坐标
 *  dir: 将要进行的搜索方向: 正东 1; 正南 2; 正西3;  正北  4;
 */

public class Position {

    private int   row;
    private int   col;
    private byte  dir;

    public Position() {
        row = 0;
        col = 0;
        dir = 0;
    }

    public Position(int row, int col, byte dir) {
        this.row = row;
        this.col = col;
        this.dir = dir;
    }

    public Position(int row, int col) {
        this(row, col, 0);
    }

    public Position(int row, int col, int dir) {
        this(row, col, (byte)dir);
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public short getDir() {
        return dir;
    }

    public String toString() {
        String dirStr = "";
        switch (dir) {
          case 1:  dirStr = "正东"; break;
          case 2:  dirStr = "正南"; break;
          case 3:  dirStr = "正西"; break;
          case 4:  dirStr = "正北"; break;
          default: dirStr = "UNKNOWN"; break;
        }
        return "(" + row + "," + col + "," + dirStr + ")";
    }

    public boolean equals(Object obj)
    {
        if (obj == this) { return true; }
        if (obj instanceof Position) {
            Position p = (Position) obj;
            if (p.row == this.row && p.col == this.col && p.dir == this.dir) {
                return true;
            }
        }
        return false;
    }

    public int hashCode()
    {
        int result = 17;
        result = result * 31 + row;
        result = result * 31 + col;
        result = result * 31 + dir;
        return result;
    }

}

4.  迷宫的核心实现 Maze :

 里面注释说的比较清楚了,有几个技巧说明一下: (1)  由于要使用回溯算法,必须使用一个 Map<Position, List<triedDirs>> 来记录每个位置已经尝试过的方向,使用一个栈 stackForCreate 记录当前行进的位置轨迹; 当回溯到前面的位置时,不再重复已经尝试过的方向,避免重复尝试陷入无限循环; (2) 方向选择上,耗费了一点空间,简单地实现了方向选择的概率设置; (3) 在抵达迷宫边界时,对方向加以限制,只允许往出口方向走;否则,回走会形成环路,由于回溯的特性,会将环路里面的墙全部"吃掉"! (4) 在迷宫展示上,为了简便使用了字符 IIII 完美等于 5 个空格, 实现了对齐问题; 虽然使用等宽字体,但似乎未起作用, 也尝试过 T, [T], [I], 这样的符号,但与空格难以对齐。写这个程序还是费了不少心思的 ^_^ 注意到 Maze 继承了 Observable , 支持 GUI 展示, 可以展示迷宫是如何生成的 (虽然最终样子不太好看), 也可以看到空格是如何一步步"吃掉"由 IIII 组成的墙的, interesting ~~

package zzz.study.javagui.maze;

import java.util.*;
import java.util.concurrent.TimeUnit;

public class Maze extends Observable {

    // 定义迷宫大小:行数 rows 和列数 cols
    private final int rows;
    private final int cols;

    // 定义迷宫出口点位置: 行坐标 EXIT_ROW 和 列坐标 EXIT_COL
    private final int EXIT_ROW;
    private final int EXIT_COL;

    // 定义迷宫矩阵mazeMatrix 和 标记数组 mark
    private boolean[][] mazeMatrix;   // true: 可通行;  false: 不可通行
    private short[][] mark;

    private String mazeStr = "";      // 迷宫的字符串表示
    private String solution = "";     // 迷宫的解的字符串表示

    // 定义移动方向表
    private byte[][] move = {
            {0, 1},        // 正东 , move[0]  方向一
            {1, 0},        // 正南 , move[1]  方向二
            {0, -1},       // 正西 , move[2]  方向三
            {-1, 0},       // 正北 , move[3]  方向四
    };

    // 存放所有方向, 使用该集合与某个位置已尝试方向的差集来获取其未尝试的方向
    private static final Set<Byte> allDirs = new HashSet<Byte>(Arrays.asList(new Byte[] {0, (byte)1, (byte)2, (byte)3}));

    private DyStack<Position> stack;    // 使用栈存放迷宫通路路径
    private DyStack<Position> stackForCreate; // 使用栈存放创建迷宫时的位置集合

    private boolean isCreatedFinished;   // 迷宫是否创建完成

    private Random rand = new Random();

    public Maze(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        EXIT_ROW = rows - 1;
        EXIT_COL = cols - 1;
        mazeMatrix = new boolean[rows][cols];
    }

    /**
     * 迷宫求解:求解迷宫并设置解的表示
     */
    public void solve() {
        if (hasPath()) {
            setSolutionStr();
        } else {
            noSolution();
        }
    }

    /**
     * 迷宫矩阵的字符串表示
     */
    public String toString() {

        StringBuilder mazeBuf = new StringBuilder("\n");
        String mazeCell = "";
        for (int i = 0; i < rows; i++) {
            if (i == 0) {
                mazeBuf.append("Entrance => ");
            } else {
                // the width of "Entrance => " is Equal to the width of 20 spaces.
                mazeBuf.append(indent(20));
            }
            mazeBuf.append(‘|‘);
            for (int j = 0; j < cols; j++) {
                if (mazeMatrix[i][j] == false) {
                    mazeCell = String.format("%4s", "IIII");
                } else {  // 存在通路
                    mazeCell = String.format("%5s", "");
                }
                mazeBuf.append(mazeCell);
            }
            if (i == rows - 1) {
                mazeBuf.append("| => Exit\n");
            } else {
                mazeBuf.append("|\n");
            }
        }
        mazeStr = mazeBuf.toString();
        return mazeStr;
    }

    /**
     * 监听按钮事件后发生改变,并通知观察者此变化的发生
     */
    public void change() {
        setChanged();
        notifyObservers();
    }

    public String getSolution() {
        return solution;
    }

    public boolean isCreatedFinished() { return isCreatedFinished; }

    /**
     * 将迷宫还原为初始状态
     */
    public void reset() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                mazeMatrix[i][j] = rand.nextBoolean();
            }
        }
        isCreatedFinished = false;
    }

    /*
     * 生成迷宫, 采用 Recursive Backtracking. Refer to:
     * <a href="http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking"/>
     */
    public void createMaze() {
        stackForCreate = new DyStack<Position>(rows + cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {   // 初始无通路
                mazeMatrix[i][j] = false;
            }
        }

        mazeMatrix[0][0] = true;

        int currRow = 0;
        int currCol = 0;
        byte nextdir = 0;                  // 当前可能选择的方向
        int nextRow = currRow;             // 下一个可能到达的相邻位置
        int nextCol = currCol;

        // 每个位置已经尝试过的方向,用于回溯时确定有效的下一个方向
        Map<Position, Set<Byte>> triedPaths = new HashMap<Position, Set<Byte>>();

        List<Byte> allDirsWalked = new ArrayList<Byte>();

        while (currRow != EXIT_ROW || currCol != EXIT_COL) {

            do {
                nextdir = getNextRandDir(currRow, currCol, triedPaths);
                allDirsWalked.add(nextdir);
                while (nextdir == -1) {
                    Position p = stackForCreate.pop();
                    currRow = p.getRow();
                    currCol = p.getCol();
                    nextdir = getNextRandDir(currRow, currCol, triedPaths);
                    allDirsWalked.add(nextdir);
                    System.out.println("Back to: " + p);
                }

                nextRow = currRow + move[nextdir][0];             // 取得下一个可能到达的相邻位置
                nextCol = currCol + move[nextdir][1];
                addTriedPaths(currRow, currCol, nextdir, triedPaths);

                System.out.println(currRow + " " + currCol + " " + nextdir + " " + nextRow + " " + nextCol);

            } while(!checkBound(nextRow, nextCol));

            // 已尝试过的路径, 分两种情况: 所有方向都尝试过或仍有方向没有尝试过
            // 如果所有方向都尝试过, 那么需要回退到上一个位置再尝试
            if (mazeMatrix[nextRow][nextCol]) {
                if (hasAllPathTried(currRow, currCol, triedPaths)) {
                    Position p = stackForCreate.pop();
                    currRow = p.getRow();
                    currCol = p.getCol();
                    System.out.println("Back to: " + p);
                }
                continue;
            }

            mazeMatrix[nextRow][nextCol] = true;
            stackForCreate.push(new Position(currRow, currCol, nextdir));
            currRow = nextRow;
            currCol = nextCol;

            // 更新 UI 界面, 显示迷宫当前状态
            try {
                change();
                TimeUnit.MILLISECONDS.sleep(300);
            } catch (InterruptedException ie) {
                System.err.println("pause between maze-creating steps interrupted");
            }
        }

        mazeMatrix[EXIT_ROW][EXIT_COL] = true;
        isCreatedFinished = true;
        change();

        statDirWalked(allDirsWalked);
    }

    /*
     * 当前位置的所有方向是否都已经尝试过
     */
    private boolean hasAllPathTried(int currRow, int currCol, Map<Position, Set<Byte>> triedPaths) {
        Set<Byte> triedDirs = triedPaths.get(new Position(currRow, currCol));
        if (triedDirs == null) {
            triedDirs = new HashSet<Byte>();
        }
        Set<Byte> allDirsCopy = new HashSet<Byte>(allDirs);
        allDirsCopy.removeAll(triedDirs);
        return allDirsCopy.isEmpty();
    }

    /*
     * 记录当前位置已经尝试过的方向, 避免后续走重复路子
     */
    private void addTriedPaths(int currRow, int currCol, byte nextdir, Map<Position, Set<Byte>> triedPaths) {
        Position currPos = new Position(currRow, currCol);
        Set<Byte> triedDirs = triedPaths.get(currPos);
        if (triedDirs == null) {
            triedDirs = new HashSet<Byte>();
        }
        triedDirs.add(nextdir);
        triedPaths.put(currPos, triedDirs);
    }

    // 抵达迷宫最上边界时, 仅允许往东或往南走
    private static final byte[] firstRowAllowedDirs = new byte[] { (byte)0, (byte)1 };

    // 抵达迷宫最下边界时, 仅允许往东或往北走
    private static final byte[] lastRowAllowedDirs = new byte[] { (byte)0, (byte)3 };

    // 抵达迷宫最左边界时, 仅允许往东或往南走
    private static final byte[] firstColAllowedDirs = new byte[] { (byte)0, (byte)1 };

    // 抵达迷宫最右边界时, 仅允许往南或往西走
    private static final byte[] lastColAllowedDirs = new byte[] { (byte)1, (byte)2 };

    /*
     * 获取下一个随机的方向, [0,1,2,3] , 若均已尝试, 返回 -1
     */
    private byte getNextRandDir(int currRow, int currCol, Map<Position, Set<Byte>> triedPaths) {
        Set<Byte> triedDirs = (Set<Byte>) triedPaths.get(new Position(currRow, currCol));
        if (triedDirs == null) {
            triedDirs = new HashSet<Byte>();
        }

        // 如果抵达迷宫边界, 则优先向出口方向走, 避免回走会形成环路, 破坏所有的墙
        if (currRow == 0) {
            if (triedDirs.contains(firstColAllowedDirs[0]) && triedDirs.contains(firstRowAllowedDirs[1])) {
                return -1;
            }
            return firstRowAllowedDirs[rand.nextInt(2)];
        }

        if (currRow == EXIT_ROW) {
            if (triedDirs.contains(lastRowAllowedDirs[0]) && triedDirs.contains(lastRowAllowedDirs[1])) {
                return -1;
            }
            return lastRowAllowedDirs[rand.nextInt(2)];
        }

        if (currCol == 0) {
            if (triedDirs.contains(firstColAllowedDirs[0]) && triedDirs.contains(firstColAllowedDirs[1])) {
                return -1;
            }
            return firstColAllowedDirs[rand.nextInt(2)];
        }

        if (currCol == EXIT_COL) {
            if (triedDirs.contains(lastColAllowedDirs[0]) && triedDirs.contains(lastColAllowedDirs[1])) {
                return -1;
            }
            return lastColAllowedDirs[rand.nextInt(2)];
        }

        Set<Byte> allDirsCopy = new HashSet<Byte>(allDirs);
        allDirsCopy.removeAll(triedDirs);
        List<Byte> possibleDirs = getRandomDirs(allDirsCopy);
        Byte[] nonTriedDirs = possibleDirs.toArray(new Byte[possibleDirs.size()]);
        if (nonTriedDirs.length == 0) {
            return -1;
        }
        else {
            byte nextdir = nonTriedDirs[rand.nextInt(nonTriedDirs.length)];
            return nextdir;
        }
    }

    /*
     * 统计随机选择的方向出现的比例
     */
    private void statDirWalked(List<Byte> allDirWalked) {
        int[] counts = new int[4];
        int backCount = 0;
        for (Byte b: allDirWalked) {
            if (b != -1) {
                counts[b] += 1;
            }
            else {
                backCount++;
            }
        }
        int total = allDirWalked.size();
        for (int i=0; i < counts.length; i++) {
            System.out.printf("P[%d]=%g ", i, (double)counts[i] / total);
        }
        System.out.println("back count: " + backCount);
        System.out.println(allDirWalked);
    }

    // 各方向出现的概率设置,
    private static final int P0 = 30;
    private static final int P1 = 25;
    private static final int P2 = 25;
    private static final int P3 = 20;

    /*
     * 扩展 nonTriedDirs 使得 0 (向前) , 1 (向下) 出现的概率更大一些, 减少回退的几率
     */
    private List<Byte> getRandomDirs(Set<Byte> nonTriedDirs) {

        List<Byte> selectDirs = new ArrayList<Byte>();
        if (nonTriedDirs.contains((byte)0)) {
            selectDirs.addAll(createNnums((byte) 0, P0));
        }
        if (nonTriedDirs.contains((byte)1)) {
            selectDirs.addAll(createNnums((byte) 1, P1));
        }
        if (nonTriedDirs.contains((byte)2)) {
            selectDirs.addAll(createNnums((byte) 2, P2));
        }
        if (nonTriedDirs.contains((byte)3)) {
            selectDirs.addAll(createNnums((byte) 3, P3));
        }

        System.out.println(selectDirs);
        return selectDirs;
    }

    private static List<Byte> createNnums(byte b, int num) {
        List<Byte> occurs = new ArrayList<Byte>();
        for (int i=0; i<num; i++) {
            occurs.add(b);
        }
        return occurs;
    }

    private boolean checkBound(int row, int col) {
        return ((row < rows && row >= 0) && (col < cols && col >= 0));
    }

    /*
     * 求解迷宫路径
     */
    private boolean hasPath() {
        int row = 0, col = 0, dir = 0;           // 当前位置的行列位置坐标及搜索移动方向
        int nextRow, nextCol;              // 下一步移动要到达的位置坐标
        boolean found = false;
        Position position = new Position(0, 0, (byte) 0);       // 通道的临时存放点
        stack = new DyStack<Position>(rows + cols);            // 创建指定容量的空栈
        mark = new short[rows][cols];
        mark[0][0] = 1;
        stack.push(position);

        while (!stack.isEmpty() && !found) {
            try {
                position = stack.pop();                       // 如四个搜索方向的相邻位置都无通道,则出栈并退回到最近一次经过的位置
                row = position.getRow();
                col = position.getCol();
                dir = position.getDir();
                while (dir < 4 && !found) {
                    nextRow = row + move[dir][0];             // 取得下一个可能到达的相邻位置
                    nextCol = col + move[dir][1];

                    if (nextRow == EXIT_ROW && nextCol == EXIT_COL) {   // 找到出口点,即存在通路径
                        found = true;
                        position = new Position(row, col, (byte) ++dir);
                        stack.push(position);
                        position = new Position(EXIT_ROW, EXIT_COL, (byte) 1);
                        stack.push(position);
                    } else if (checkBound(nextRow, nextCol) && mazeMatrix[nextRow][nextCol] == true && mark[nextRow][nextCol] == 0) {
                        // 没有找到出口点,但当前搜索方向的相邻位置为通道,则前进到相邻位置,并在相邻位置依序按照前述四个方向进行搜索移动
                        mark[nextRow][nextCol] = 1;
                        position = new Position(row, col, (byte) ++dir);
                        stack.push(position);
                        row = nextRow;
                        col = nextCol;
                        dir = 0;
                    } else {
                          /* 没有找到出口点,且当前搜索方向的相邻位置为墙,或已搜索过,或超出迷宫边界,
                           * 则向当前位置的下一个搜索方向进行搜索移动       */
                        ++dir;
                    }
                }
            } catch (Exception e) {
                System.out.print("栈空!");
                e.printStackTrace();
            }
        }

        if (found)
            return true;
        else
            return false;

    }

    private void setSolutionStr() {
        solution = "\n所找到的通路路径为: \n" + stack + "\n\n";
        solution += "其中,(x,y,z)表示从坐标点(x,y)向z方向移动\n\n";
    }

    private void noSolution() {  // 迷宫无解的字符串表示
        solution = "迷宫无解!\n";
    }

    /*
     * 显示迷宫时,为美观起见, 缩进 n 个字符
     */
    private String indent(int n) {
        StringBuilder indentBuf = new StringBuilder();
        while (n-- > 0) {
            indentBuf.append(‘ ‘);
        }
        return indentBuf.toString();
    }

}

  5.  GUI 界面: 主要使用 "观察者" 模式来实现。其中 Maze 是被观察者, 当 Maze 发生变化时,会去通知后面会给出的观察者 MazePanel ; 而 Maze 的触发是在 Model 类里。

  Model 类: 监听按钮点击事件, 获取输入来触发生成迷宫。 注意到这里另起了线程去执行, 使得在 maze.CreateMaze 方法里的 sleep 不会阻塞 Ui 线程更新界面; 写 GUI 记住两句话: (1) 更新组件和界面相关的事情一定要在事件分发线程里做; 与界面无关的计算和 IO 不要在事件分发线程里做,因为那样会阻塞 UI 线程,导致界面无法更新(假死); (2) 事件处理方法 actionPerformed 和 SwingUtilities.invokeLater 里的代码是在事件分发线程里做的;

package zzz.study.javagui.maze;

import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Observer;
import java.util.regex.Pattern;

import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JTextField;

/**
 * 监听按钮事件,并改变 Maze 对象(被观察者)
 */
public class Model implements ActionListener  {

    private MazeGUI app;   // 用于从中获取数据的 GUI 界面

    public void actionPerformed(ActionEvent event) {

        JTextField inputRow = app.getInputRow();
        JTextField inputCol = app.getInputCol();
        JPanel mazePanel = app.getMazePanel();

        String rowStr = inputRow.getText();
        String colStr = inputCol.getText();
        String regex = "^\\s*[1-9][0-9]?\\s*$";
        if (rowStr.matches(regex) && colStr.matches(regex)) {
           int rows = Integer.parseInt(inputRow.getText());
           int cols = Integer.parseInt(inputCol.getText());
           final Maze maze = new Maze(rows,cols);
           maze.addObserver((Observer) mazePanel);

           new Thread(new Runnable() {
               public void run() {
                   if (maze.isCreatedFinished()) {
                       maze.reset();
                       maze.change();
                   }
                   maze.createMaze();
               }
           }).start();

        }
        else {
           JOptionPane.showMessageDialog(null, "对不起,您的输入有误, 请输入 [1-99] 之间的任意数字!", "警告", JOptionPane.WARNING_MESSAGE);
        }

    }

    public void setGUI(MazeGUI app) {
        this.app = app;
    } 

}

  6.  MazePanel :  Maze 的观察者, 当 Maze 状态发生变化时,调用 change 方法时,就会通知该面板更新其显示。注意到更新 UI 在 SwingUtilities.invokeLater 方法中完成;其它事情则在外面做。

package zzz.study.javagui.maze;

import java.awt.BorderLayout;
import java.awt.Font;
import java.util.Observable;
import java.util.Observer;

import javax.swing.*;
import javax.swing.border.TitledBorder;

/**
 * 迷宫面板: 按钮事件的观察者
 */
public class MazePanel extends JPanel implements Observer {

    private String title;
    private String text;
    private JTextArea infoArea;

    public MazePanel(String title, Font font) {
        this(title, "");
        infoArea.setFont(font);
    }

    public MazePanel(String title, String text) {
        this.title = title;
        this.text = text;
        infoArea = new JTextArea(text);
        //infoArea.setEnabled(false);
        setLayout(new BorderLayout());
        setBorder(new TitledBorder(title));
        add(infoArea, BorderLayout.CENTER);
        add(new JScrollPane(infoArea));
    }

    public String getTitle() {
        return title;
    }

    public void setTitle(String title) {
        this.title = title;
    }

    public String getText() {
        return text;
    }

    public void setText(String text) {
        this.text = text;
    }

    public void update(Observable o, Object arg) {

        Maze m = (Maze)o;
        if (m.isCreatedFinished()) {
            m.solve();
            text = "" + m + "\n" + m.getSolution();
        }
        else {
            text = "" + m + "\n";
        }
        infoArea.setText(text);

        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                updateUI();
            }
        });

    }

}

  7.   MazeGUI 界面: 组装界面组件, 启动应用。

package zzz.study.javagui.maze;

import java.awt.BorderLayout;
import java.awt.Container;
import java.awt.FlowLayout;
import java.awt.Font;
import java.util.Enumeration;

import javax.swing.*;
import javax.swing.border.TitledBorder;
import javax.swing.plaf.FontUIResource;

/**
 * 迷宫程序的主界面
 * @author shuqin1984
 */
public class MazeGUI extends JFrame  {

    private JTextField inputRow;               // 用户输入行数
    private JTextField inputCol;               // 用户输入列数

    private JPanel mazePanel;                  // 显示迷宫的面板

    public MazeGUI() {
        super("程序演示:模拟走迷宫");
    }

    private final Font font = new Font("Monospaced",Font.PLAIN, 14);

    public static void main(String[] args) {

        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                MazeGUI app = new MazeGUI();
                app.launch();
            }
        });
    }

    private static void InitGlobalFont(Font font) {
        FontUIResource fontRes = new FontUIResource(font);
        for (Enumeration<Object> keys = UIManager.getDefaults().keys();
             keys.hasMoreElements(); ) {
            Object key = keys.nextElement();
            Object value = UIManager.get(key);
            if (value instanceof FontUIResource) {
                UIManager.put(key, fontRes);
            }
        }
    }

    /**
     * 启动应用程序
     */
    public void launch()
    {
        JFrame f = new MazeGUI();
        f.setBounds(100, 100, 800, 600);
        f.setVisible(true);
        f.setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE);

        InitGlobalFont(font);

        Container contentPane = f.getContentPane();
        contentPane.setLayout(new BorderLayout());

        JPanel inputPanel = createInputPanel();
        contentPane.add(inputPanel, BorderLayout.NORTH);    

        mazePanel = new MazePanel("显示迷宫和迷宫的解", font);
        contentPane.add(mazePanel, BorderLayout.CENTER);

        f.setContentPane(contentPane);
    }

    /**
     * 创建并返回输入面板
     */
    public JPanel createInputPanel() {    

        JPanel inputPanel = new JPanel(new FlowLayout());
        inputPanel.setBorder(new TitledBorder("用户输入信息提示"));

        JLabel labelInfo = new JLabel("请输入迷宫大小:",null,SwingConstants.LEFT);

        JLabel labelRow = new JLabel("行");
        JLabel labelCol = new JLabel("列");
        JLabel labelSpace = new JLabel("  ");
        if (inputRow == null)
            inputRow = new JTextField(3);
        if (inputCol == null)
            inputCol = new JTextField(3);

        inputPanel.add(labelInfo);
        inputPanel.add(inputRow);
        inputPanel.add(labelRow);
        inputPanel.add(inputCol);
        inputPanel.add(labelCol);
        inputPanel.add(labelSpace);    

        JButton button = new JButton("生成迷宫");
        inputPanel.add(button);

        Model m = new Model();
        m.setGUI(this);
        button.addActionListener(m);

        return inputPanel;

    }

    public JTextField getInputRow() {
        return inputRow;
    }

    public JTextField getInputCol() {
        return inputCol;
    }

    public JPanel getMazePanel() {
        return mazePanel;
    }

}

  【本文完】

时间: 05-07

栈与回溯:迷宫问题的相关文章

栈的运用---迷宫

实验2-1 栈与迷宫求解 [实验目的] 1.熟悉C语言的上机环境VC6,掌握C语言程序设计方法与特点. 2.掌握栈的顺序存储结构的定义及C语言实现. 3.掌握栈的顺序存储结构上的各种基本操作. 4.应用栈实现迷宫通路算法. 5.迷宫求解的关键结构定义及C语言实现. [问题说明] 一个迷宫可用n阶方阵表示,1表示能通过,0 表示不能通过.现假设老鼠从左上角[1,1]进入迷宫,编写算法,寻求一条从右下角[n,n] 出去的路径.下图是一个迷宫的示意图: 迷宫示意图 [算法基本思想] 迷宫求解是栈的一个

栈的应用-迷宫解题

总结:这个是网上找的,下面一个是我在他基础上修改的. /* 二. 栈的应用-迷宫解题 */ #include<stdio.h> #include<malloc.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //坐标类型 typedef struct { int x; in

用栈实现的迷宫问题

迷宫问题中为了保证任何位置上都能沿原路退回,显然需要用一个先进后出的结果来保存从入口到当前位置的路径.因此,在迷宫通路的算法中应用“栈”也是自然而然的事情 头文件: #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define MYOVERFLOW -2 typedef i

3-4-迷宫寻路-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版

课本源码部分 第3章  栈和队列 - 迷宫寻路 ——<数据结构>-严蔚敏.吴伟民版        源码使用说明  链接??? <数据结构-C语言版>(严蔚敏,吴伟民版)课本源码+习题集解析使用说明        课本源码合辑  链接??? <数据结构>课本源码合辑        习题集全解析  链接??? <数据结构题集>习题解析合辑        本源码引入的文件  链接? Status.h.SequenceStack.c        相关测试数据下载

搜索入门之dfs--经典的迷宫问题解析

今天来谈一下dfs的入门,以前看到的dfs入门,那真的是入门吗,都是把dfs的实现步骤往那一贴,看完是知道dfs的步骤了,但是对于代码实现还是没有概念.今天准备写点自己的心得,真的是字面意思--入门. DFS,即深度优先搜索,是一种每次搜索都向尽可能深的地方去搜索,到达尽头时再回溯进行其他结点去搜索的搜索策略.形象的说,这是一种“不撞南墙不回头”的策略. 其实也就是遍历,只不过不像一个线性数组的遍历那么直观罢了.说到回溯,每次看到这个词我都得思考一会,到底是怎么用栈进行回溯的呢?今天实际操作了一

数据结构之迷宫问题求解(二)迷宫的最短路径

上篇文章我们讨论了,迷宫问题的普通求解问题,这篇文章我们继续深入,求迷宫的最短路径. 要想求迷宫的最短路径,一个很简单的方法就是再设置一个Min栈,用来放最短路径,每找到一个出口,就将path栈与Min栈进行比较,如果path栈更小,则赋值给Min. 而在上篇文章中,我们将走过的路径做了标记,每走一个坐标,就把那个坐标置为3,直至找到出口. 因此如果用这种标记方式,显然是会出现问题的. 所以我们需要换种标记方式! 最终....我决定,使出口的值为2,每走一步使当前位置标记变为是上一位置标记再加1

Linux Kernel - Debug Guide (Linux内核调试指南 )

http://blog.csdn.net/blizmax6/article/details/6747601 linux内核调试指南 一些前言 作者前言 知识从哪里来 为什么撰写本文档 为什么需要汇编级调试 ***第一部分:基础知识*** 总纲:内核世界的陷阱 源码阅读的陷阱 代码调试的陷阱 原理理解的陷阱 建立调试环境 发行版的选择和安装 安装交叉编译工具 bin工具集的使用 qemu的使用 initrd.img的原理与制作 x86虚拟调试环境的建立 arm虚拟调试环境的建立 arm开发板调试环

Linux内核设计与实现读书笔记——第十八章

第18章 调试 调试工作艰难是内核级开发区别于用户级开发的一个显著特点,相比于用户级开发,内核调试的难度确实要艰苦得多.更可怕的是,它带来的风险比用户级别更高,内核的一个错误往往立刻就能让系统崩溃. 18.1 准备开始 一个bug.听起来很可笑,但确实需要一个确定的bug.如果错误总是能够重现的话,那对我们会有很大的帮助(有一部分错误确实如此).然而不幸的是,大部分bug通常都不是行为可靠而且定义明确的. 一个藏匿bug的内核版本.如果你知道这个bug最早出现在哪个内核版本中那就再理想不过了.

【深入浅出jQuery】源码浅析--整体架构(转)

最近一直在研读 jQuery 源码,初看源码一头雾水毫无头绪,真正静下心来细看写的真是精妙,让你感叹代码之美. 其结构明晰,高内聚.低耦合,兼具优秀的性能与便利的扩展性,在浏览器的兼容性(功能缺陷.渐进增强)优雅的处理能力以及 Ajax 等方面周到而强大的定制功能无不令人惊叹. 另外,阅读源码让我接触到了大量底层的知识.对原生JS .框架设计.代码优化有了全新的认识,接下来将会写一系列关于 jQuery 解析的文章. 我在 github 上关于 jQuery 源码的全文注解,感兴趣的可以围观一下