本文共 5719 字，大约阅读时间需要 19 分钟。

回溯法解迷宫（利用栈的性质进行迷宫求解）

一、迷宫类：

package migongqiujie;

import java.awt.BorderLayout;

import java.awt.Color; import java.awt.GridLayout; import java.awt.Window; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.geom.FlatteningPathIterator; import java.util.ArrayList; import java.util.Iterator; import java.util.Random; import java.util.Stack;

import javax.swing.JButton;

import javax.swing.JFrame; import javax.swing.JOptionPane; import javax.swing.JPanel;

import org.omg.CORBA.PRIVATE_MEMBER;

import org.omg.CORBA.PUBLIC_MEMBER; /* * 回溯法解迷宫（穷举法） * 实现思路： * 1、运用java Swing生成一个迷宫面板，使用Cell继承面板实现迷宫中的每个方块 * 2、生成迷宫主要是用了随机数的生成 * 3、解迷宫主要是运用了穷举法，构造栈来存放走过的路径，同时对相应的Cell块进行涂色， * 如果遇到走不通或者走过的地方都要进行出栈，同时对另一个方向进行探索。 */

public class Migong2 extends JFrame {

private int M = 30;// 设置面板为30*30 private Cell[][] cells = new Cell[M][M];// 引入Cell类 private JButton jbCreate = new JButton(“生成迷宫”); private JButton jbFindPath = new JButton(“寻找解法”); private JPanel jpUp, jpBut; private Thread th1 = new Thread(); int row, col;

public Migong2(int row, int col) {    this.row = row;    this.col = col;}public Migong2() {    super();    setSize(700, 700);    setTitle("回溯法解迷宫");    setResizable(false);    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);    setLocationRelativeTo(null);    jpUp = new JPanel();    jpBut = new JPanel();    jpUp.setLayout(new GridLayout(M, M, 2, 2));    for (int i = 0; i < M; i++) {        for (int j = 0; j < M; j++) {            cells[i][j] = new Cell(i, j);            jpUp.add(cells[i][j]);        }    }    for (int i = 0; i < M; i++)// 为迷宫增加边框    {        cells[0][i].setBackground(Color.red);        cells[M - 1][i].setBackground(Color.red);        cells[i][0].setBackground(Color.red);        cells[i][M - 1].setBackground(Color.red);    }    cells[1][0].setBackground(Color.green);// 入口    cells[28][29].setBackground(Color.green);// 出口    add(jpUp, BorderLayout.CENTER);    jpBut.add(jbCreate);    jpBut.add(jbFindPath);    add(jpBut, BorderLayout.SOUTH);    jbCreate.addActionListener(new ActionListener() {// 为生成迷宫添加事件函数        @Override        public void actionPerformed(ActionEvent e) {            th1.suspend();            CreatePath();        }    });    jbFindPath.addActionListener(new ActionListener() {// 为找解添加事件函数                @Override                public void actionPerformed(ActionEvent e) {                    th1.suspend();                    FindPath();                }            });    setVisible(true);}public void CreatePath()// 生成迷宫的图样，JbCreate的函数调用{    for (int rrow = 1; rrow < M - 1; rrow++) {// 每次生成迷宫刷新        for (int rcol = 1; rcol < M - 1; rcol++) {            cells[rrow][rcol].setBackground(Color.black);        }    }    Random random = new Random();    int row;    int col;    int i = 250;    int max = M - 2;    int min = 1;    while (i > 0) {        row = random.nextInt(max) % (max - min + 1) + min;        col = random.nextInt(max) % (max - min + 1) + min;        cells[row][col].setBackground(Color.red);        i--;    }}public void FindPath()// 解迷宫，做为jbFindPath的函数调用{    final Stack
   
     stack = new Stack
    
     ();// 构造空栈Migong2类型的空栈    Runnable runable = new Runnable() {        public void run() {            int i = 1;            int j = 1;            Cell cell = new Cell(i, j);            cells[i][j].setBackground(Color.green);            stack.push(new Migong2(i, j));            while (!stack.empty()) {// 栈不空，执行循环                try {                    Thread.sleep(50);                } catch (InterruptedException e) {                    e.printStackTrace();                }                if (cells[i][j + 1].getBackground() == Color.black) {                    cells[i][j + 1].setBackground(Color.green);                    stack.push(new Migong2(i, j + 1));                    j++;                } else if (cells[i + 1][j].getBackground() == Color.black) {                    cells[i + 1][j].setBackground(Color.green);                    stack.push(new Migong2(i + 1, j));                    i++;                } else if (cells[i][j - 1].getBackground() == Color.black) {                    cells[i][j - 1].setBackground(Color.green);                    stack.push(new Migong2(i, j - 1));                    j--;                } else if (cells[i - 1][j].getBackground() == Color.black) {                    cells[i - 1][j].setBackground(Color.green);                    stack.push(new Migong2(i - 1, j));                    i--;                } else {                    Migong2 maze = stack.pop();// 出栈                    int m;                    int n;                    m = maze.row;// 取出出栈元素的行标                    n = maze.col;// 取出出栈元素的列标                    cells[m][n].setBackground(Color.blue);                    if (stack.empty()) {                        break;                    }                    i = stack.peek().row;// 取栈顶元素的行标                    j = stack.peek().col;// 取栈顶元素的列标                    cells[i][j].setBackground(Color.blue);                }                if (i == M - 2 && j == M - 2) {                    JOptionPane.showMessageDialog(null, "找到出口了！", "",                            JOptionPane.ERROR_MESSAGE);                    return;                }            }            JOptionPane.showMessageDialog(null, "没找到出口！", "",                    JOptionPane.ERROR_MESSAGE);        }    };    th1 = new Thread(runable);    th1.start();}public static void main(String[] args) {    new Migong2();}
    
   

}

二、Cell类： package migongqiujie;

import java.awt.Color;

import java.awt.event.MouseAdapter; import java.awt.event.MouseEvent;

import javax.swing.JPanel;

public class Cell extends JPanel{ Cell(int row,int col){ setBackground(Color.black); } } 生成迷宫： 解迷宫： 无解：