用回溯法求迷宫出口

  1 package hello;
  2 
  3 import java.awt.*;
  4 import java.awt.event.ActionEvent;
  5 import java.awt.event.ActionListener;
  6 import java.util.Random;
  7 import java.util.Stack;
  8 
  9 import javax.swing.*;
 10 
 11 public class Maze extends JFrame {
 12 
 13     /**
 14      * 
 15      */
 16     private static final long serialVersionUID = 1L;
 17     /*
 18      * 界面布局
 19      */
 20     JPanel p = new JPanel(new BorderLayout());
 21     jpanelp1 p1 = new jpanelp1();
 22     JPanel p2 = new JPanel(new GridLayout(1, 2, 5, 5));
 23     Button b1 = new Button("刷新");
 24     Button b2 = new Button("寻路");
 25 
 26     /*
 27      * Launch the application.
 28      */
 29     public static void main(String[] args) {
 30         Maze frame = new Maze();
 31         frame.setTitle("七彩迷宫");
 32         frame.setSize(700, 700);
 33         frame.setLocationRelativeTo(null);
 34         frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
 35         frame.setVisible(true);
 36     }
 37 
 38     /*
 39      * Create the frame.
 40      */
 41     public Maze() {
 42         add(p);
 43         p.add(p1, BorderLayout.CENTER);
 44         p.add(p2, BorderLayout.SOUTH);
 45         p2.add(b1);
 46         p2.add(b2);
 47         b1.addActionListener(new refreshListener());
 48         b2.addActionListener(new findPathListener());
 49 
 50     }
 51 
 52     /*
 53      * refreshListener
 54      */
 55     class refreshListener implements ActionListener {
 56         public void actionPerformed(ActionEvent e) {
 57             // p1.removeAll();
 58             // p1.repaint();
 59             // p1.init();
 60             p.removeAll();
 61             p.repaint();
 62             p1 = new jpanelp1();
 63             p.add(p1, BorderLayout.CENTER);
 64             p.add(p2, BorderLayout.SOUTH);
 65             p.updateUI();
 66         }
 67     }
 68 
 69     /*
 70      * findPathListener
 71      */
 72     class findPathListener implements ActionListener {
 73         public void actionPerformed(ActionEvent e) {
 74             p1.findPath();
 75         }
 76     }
 77 
 78     class Position {
 79         public Position() {
 80 
 81         }
 82 
 83         public Position(int row, int col) {
 84             this.col = col;
 85             this.row = row;
 86         }
 87 
 88         public String toString() {
 89             return "(" + row + " ," + col + ")";
 90         }
 91 
 92         int row;
 93         int col;
 94     }
 95 
 96     /*
 97      * maze JPanel
 98      */
 99     class jpanelp1 extends JPanel {
100         /**
101          * 
102          */
103         private static final long serialVersionUID = 1L;
104         JButton buttons[][];
105         int ibuttons[][];
106         boolean bbuttons[][];
107         Stack<Position> stack;
108 
109         public jpanelp1() {
110             setLayout(new GridLayout(18, 18));
111             stack = new Stack<Position>();
112             buttons = new JButton[18][18];
113             ibuttons = new int[18][18]; // 存放迷宫数值
114             bbuttons = new boolean[18][18]; // 存放迷宫访问值
115             init();
116         }
117 
118         // 初始化函数
119         public void init() {
120             for (int i = 0; i < 18; i++) {
121                 for (int j = 0; j < 18; j++) {
122                     buttons[i][j] = new JButton();
123                     add(buttons[i][j]);
124                     buttons[i][j].setMargin(new Insets(0, 0, 0, 0));
125                 }
126             }
127 
128             // 生成迷宫数组
129             int a;
130             for (int i = 1; i < 17; i++) {
131                 for (int j = 1; j < 17; j++) {
132                     Random random1 = new Random();
133                     a = random1.nextInt(4);
134                     if (a >= 1)
135                         a = 1;
136                     ibuttons[i][j] = a;
137                     bbuttons[i][j] = false;
138                 }
139             }
140 
141             // 给迷宫四面加墙
142             for (int i = 0; i < 18; ++i) {
143                 for (int j = 0; j < 18; ++j) {
144                     ibuttons[0][j] = ibuttons[17][j] = 0;
145                     ibuttons[i][0] = ibuttons[i][17] = 0;
146                     buttons[i][j].setBackground(Color.blue);
147                 }
148             }
149 
150             // 确定出口、入口
151             buttons[0][1].setBackground(Color.green);
152             String str1 = new String("入口");
153             buttons[0][1].setText(str1);
154             buttons[17][16].setBackground(Color.green);
155             String str2 = new String("出口");
156             buttons[17][16].setText(str2);
157             for (int i = 1; i < 17; i++) {
158                 for (int j = 1; j < 17; j++) {
159                     {
160                         // 显示迷宫存放整形值
161                         // String s = String.valueOf(ibuttons[i][j]);
162                         // buttons[i][j].setText(s);
163                         switch (ibuttons[i][j]) {
164                         case 0:
165                             buttons[i][j].setBackground(Color.blue);
166                             break;
167                         case 1:
168                             buttons[i][j].setBackground(Color.green);
169                             break;
170                         default:
171                             break;
172                         }
173                     }
174                 }
175             }
176         }
177 
178         // 回溯法查找路线
179         public void findPath() {
180             int i = 1;
181             int j = 1;
182             bbuttons[i][j] = true;
183             if (ibuttons[i][j] != 0)
184                 stack.push(new Position(i, j));
185             while (!stack.empty() && !(i == 16 && j == 16) && i > 0 && j > 0) {
186                 if ((ibuttons[i][j + 1] != 0) && (bbuttons[i][j + 1] == false)) {
187                     bbuttons[i][j + 1] = true;
188                     stack.push(new Position(i, j + 1));
189                     j++;
190                 } else if ((ibuttons[i + 1][j] != 0)
191                         && (bbuttons[i + 1][j] == false)) {
192                     bbuttons[i + 1][j] = true;
193                     stack.push(new Position(i + 1, j));
194                     i++;
195                 } else if ((ibuttons[i][j - 1] != 0)
196                         && (bbuttons[i][j - 1] == false)) {
197                     bbuttons[i][j - 1] = true;
198                     stack.push(new Position(i, j - 1));
199                     j--;
200                 } else if ((ibuttons[i - 1][j] != 0)
201                         && (bbuttons[i - 1][j] == false)) {
202                     bbuttons[i - 1][j] = true;
203                     stack.push(new Position(i - 1, j));
204                     i--;
205                 } else {
206                     stack.pop();
207                     if (stack.empty()) {
208                         break;
209                     }
210                     i = stack.peek().row;
211                     j = stack.peek().col;
212                 }
213             }
214             if (stack.empty()) {
215                 String message = "该迷宫无出路！";
216                 JOptionPane.showMessageDialog(null, message);
217                 // 确认无路可走，再次初始化迷宫
218                 p1.removeAll();
219                 p1.init();
220             } else {
221                 int x, y;
222                 while (!stack.empty()) {
223                     x = stack.peek().row;
224                     y = stack.peek().col;
225                     buttons[x][y].setBackground(Color.red);
226                     stack.pop();
227                 }
228                 p1.repaint();
229             }
230         }
231     }
232 }