public class Main_Class {
 public static void main(String args[]) {
 PTB_Frame frame=new PTB_Frame("Push The Box");
 frame.setBounds(0,0,1200,1200);
 }
}

import java.awt.*;
import java.awt.event.*;
 
import javax.swing.*;
@SuppressWarnings("serial")
 
public class PTB_Frame extends JFrame {
 private Font font = new Font("宋體", Font.PLAIN, 23);
 private Map_Manager map_manager=new Map_Manager();
 private ConsolePanel console = new ConsolePanel(map_manager);
 private JButton creat_map=new JButton("創(chuàng)建地圖");
 private MapPanel map=new MapPanel(map_manager);
 PTB_Frame(String title) {
 init();
 this.setTitle(title);
 this.setVisible(true);
 this.setDefaultCloseOperation(EXIT_ON_CLOSE);
 }
 
 void init() {
 this.setLayout(null);
 console.setBounds(0, 0, 1200,250);
 console.add(creat_map);
 this.add(console);
 map.setBounds(80, 250, 1200, 800);
 this.add(map);
 creat_map.setFont(font);
 creat_map.addActionListener(new ActionListener() {
 public void actionPerformed(ActionEvent e) {
 console.creatMap();
 map.setMap(map_manager.getHeight(), map_manager.getWidth(), map_manager.getStepOfMap(), map_manager.getMap());
 map.creatMap();
 }
 });
 }
}

import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
 
@SuppressWarnings("serial")
public class ConsolePanel extends JPanel {
 Font font = new Font("宋體", Font.PLAIN, 23);
 JTextField t_height = new JTextField(3);
 JTextField t_width = new JTextField(3);
 JTextField t_diff = new JTextField(5);
 JButton get_path = new JButton("查看最短路徑");
 JTextArea show_path = new JTextArea(5, 40);
 int height, width;
 double diff;
 Map_Manager map_manager;
 
 ConsolePanel(Map_Manager map_manager) {
 this.map_manager = map_manager;
 UIManager.put("Label.font", font);
 this.add(new JLabel("地圖高度："));
 t_height.setFont(font);
 this.add(t_height);
 this.add(new JLabel("（3~100的整數(shù)）"));
 this.add(new JLabel("地圖寬度："));
 t_width.setFont(font);
 this.add(t_width);
 this.add(new JLabel("（3~100的整數(shù)）"));
 this.add(new JLabel("地圖難度："));
 t_diff.setFont(font);
 this.add(t_diff);
 this.add(new JLabel("（1.0~10.0之間的小數(shù)）"));
 this.add(new JLabel("注：地圖高度和寬度以及難度越大，生成地圖時間越長"));
 get_path.setFont(font);
 this.add(get_path);
 show_path.setFont(font);
 show_path.setLineWrap(true);// 自動換行
 show_path.setWrapStyleWord(true);// 換行不斷字
 JPanel show_path_panel = new JPanel();
 show_path_panel.add(new JScrollPane(show_path));//滾動窗口
 this.add(show_path_panel);
 get_path.addActionListener(new ActionListener() {
 public void actionPerformed(ActionEvent e) {
 Map_Manager.Point path[] = map_manager.getPath();
 if (path != null) {
  show_path.setText(null);
  for (int i = 0; i<map_manager.getStepOfMap(); ++i)
  show_path.append(path[i] + " ");
 }
 }
 });
 }
 
 public void creatMap() {
 try {
 height = Integer.valueOf(t_height.getText());
 width = Integer.valueOf(t_width.getText());
 diff = Double.valueOf(t_diff.getText());
 if (height < 3 || height > 100 || width < 3 || width > 100 || diff < 1 || diff > 10)
 throw new NumberFormatException();
 map_manager.setMap(height, width, diff);
 map_manager.creatMap();
 show_path.setText(null);
 } catch (NumberFormatException ex) {
 JOptionPane.showMessageDialog(getRootPane(), "參數(shù)格式不正確");
 }
 }
}

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
 
@SuppressWarnings("serial")
public class MapPanel extends JPanel {
 private Font font = new Font("宋體", Font.PLAIN, 23);
 private JPanel map_area;
 JPanel control_bar = new JPanel();
 private JButton drawback, restart,start;
 private JLabel l_min_step, l_left_step, l_passed_step;
 private JLabel show_cur_point;
 private JLabel show_cur_box;
 private Point person = new Point();
 private Point start_of_person = new Point();
 private Point start_of_box = new Point();
 private Point end = new Point();
 private Point box = new Point();
 private int width, height;
 private int map[][] = new int[100][100];
 private int di[][] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
 private int min_step, passed_step = 0;
 private Stack<Operation> operation_recorder = new Stack<Operation>();
 private JButton block[][] = new JButton[100][100];
 private Map_Manager map_manager;
 
 private class Point implements Cloneable {
 int x, y;
 
 public boolean equals(Object obj) {
 if (!(obj instanceof Point))
 return false;
 Point point = (Point) obj;
 return this.x == point.x && this.y == point.y;
 }
 
 public Object clone() {
 Point newPoint = null;
 try {
 newPoint = (Point) super.clone();
 } catch (CloneNotSupportedException e) {
 e.printStackTrace();
 }
 return newPoint;
 }
 
 public String toString() {
 return "(" + (this.x + 1) + "," + (this.y + 1) + ")";
 }
 }
 
 public void setMap(int height, int width, int min_step, int map[][]) {
 this.height = height;
 this.width = width;
 this.min_step = min_step;
 this.map = map;
 }
 private class PtbKeyAdapter extends KeyAdapter {
 public void keyPressed(KeyEvent e) {
 int keycode = e.getKeyCode();
 if (keycode == KeyEvent.VK_UP) {
 pointMove(0);
 } else if (keycode == KeyEvent.VK_DOWN) {
 pointMove(1);
 } else if (keycode == KeyEvent.VK_LEFT) {
 pointMove(2);
 } else if (keycode == KeyEvent.VK_RIGHT) {
 pointMove(3);
 }
 }
 }
 
 private class Operation {
 int stuff;// 1代表箱子，0代表人
 int dir;// 0代表上，1代表下，2代表左，3代表右
 
 Operation(int stuff, int dir) {
 this.stuff = stuff;
 this.dir = dir;
 }
 }
 
 private boolean accessible(Point point) {// point可走則返回true
 if (point.x < 0 || point.x >= height || point.y < 0 || point.y >= width)// 越界
 return false;
 if (map[point.x][point.y] == 1)// 走到墻上
 return false;
 return true;
 }
 
 private void pointMove(int dir) {
 if(passed_step>=min_step)
 return;
 // 先判斷能否進行交換，若能，則交換兩按鈕顏色值
 Point cur_point = new Point();
 cur_point.x = person.x + di[dir][0];
 cur_point.y = person.y + di[dir][1];
 if (!accessible(cur_point))// 當前點不可走
 return;
 if (cur_point.equals(box)) {
 // 當人前進方向上前一個點是箱子
 Point next_box = new Point();
 next_box.x = box.x + di[dir][0];
 next_box.y = box.y + di[dir][1];
 if (!accessible(next_box))// 箱子無法推動
 return;
 // 如果箱子能前進，則人也前進，不能則人不能前進
 go(box, dir);
 ++this.passed_step;
 updateStep();
 operation_recorder.push(new Operation(1, dir));
 }
 go(person, dir);
 show_cur_point.setText(" "+person.toString()+" ");
 operation_recorder.push(new Operation(0, dir));
 if (box.equals(end))
 JOptionPane.showMessageDialog(this.getRootPane(), "WINNER WINNER CHICKEN DINNER!");
 else if(this.passed_step==this.min_step)
 JOptionPane.showMessageDialog(this.getRootPane(), "江河猶在，命數(shù)已盡，悲哉！");
 }
 
 private void go(Point point, int dir) {// 實現(xiàn)前進部分的代碼
 Color color = block[point.x][point.y].getBackground();
 if (point.equals(end))
 block[point.x][point.y].setBackground(Color.GREEN);
 else
 block[point.x][point.y].setBackground(Color.WHITE);
 point.x += di[dir][0];
 point.y += di[dir][1];
 block[point.x][point.y].setBackground(color);
 }
 
 private void updateStep() {
 l_passed_step.setText(Integer.toString(passed_step));
 l_left_step.setText(Integer.toString(min_step - passed_step));
 show_cur_box.setText(" "+box.toString()+" ");
 }
 
 public void paintMap() {
 map_area = new JPanel(new GridLayout(this.height, this.width));
 for (int i = 0; i < this.height; i++)
 for (int j = 0; j < this.width; j++) {
 block[i][j] = new JButton();
 if (map[i][j] == 0)// 數(shù)組中0為路
  block[i][j].setBackground(Color.WHITE);
 else if (map[i][j] == 1)// 數(shù)組中1為墻
  block[i][j].setBackground(Color.BLACK);
 else if (map[i][j] == 2)// 數(shù)組中2為箱子位置
 {
  block[i][j].setBackground(Color.BLUE);
  start_of_box.x = i;
  start_of_box.y = j;
 } else if (map[i][j] == 3)// 數(shù)組中3為終點
 {
  block[i][j].setBackground(Color.GREEN);
  end.x = i;
  end.y = j;
 } else if (map[i][j] == 4) {// 數(shù)組中4為人的位置
  block[i][j].setBackground(Color.RED);
  start_of_person.x = i;
  start_of_person.y = j;
 }
 map_area.add(block[i][j]);
 }
 person = (Point) start_of_person.clone();
 box = (Point) start_of_box.clone();
 l_min_step.setText(Integer.toString(min_step));
 show_cur_point.setText(" "+person.toString()+" ");
 passed_step=0;
 updateStep();
 int map_height=750,map_width=750;
 if(this.height>this.width)
 map_width=(750/this.height)*this.width;
 else if(this.width>this.height)
 map_height=(750/this.width)*this.height;
 map_area.setBounds(0, 0, map_width, map_height);
 this.add(map_area);
 }
 
 public MapPanel(Map_Manager map_manager) {
 this.map_manager = map_manager;
 init();
 }
 
 private void init() {
 this.setLayout(null);
 map_manager.setMap(20, 20, 7.0);
 map_manager.creatMap();
 this.height = map_manager.getHeight();
 this.width = map_manager.getWidth();
 this.min_step = map_manager.getStepOfMap();
 this.map = map_manager.getMap();
 UIManager.put("Label.font", font);
 drawback = new JButton("后退一步");
 restart = new JButton("重新開始");
 start=new JButton("開始");
 control_bar.add(new JLabel("當前箱子的位置"));
 show_cur_box=new JLabel();
 control_bar.add(show_cur_box);
 control_bar.add(new JLabel("當前人的位置"));
 show_cur_point=new JLabel();
 control_bar.add(show_cur_point);
 control_bar.add(new JLabel("最短步數(shù)："));
 l_min_step = new JLabel();
 l_min_step.setFont(font);
 control_bar.add(l_min_step);
 control_bar.add(new JLabel("已走步數(shù)："));
 l_passed_step = new JLabel();
 l_passed_step.setFont(font);
 control_bar.add(l_passed_step);
 control_bar.add(new JLabel("剩余步數(shù)："));
 l_left_step = new JLabel();
 l_left_step.setFont(font);
 control_bar.add(l_left_step);
 control_bar.add(new JLabel("注：這里的步數(shù)是"));
 control_bar.add(new JLabel("箱子移動的步數(shù)"));
 control_bar.add(new JLabel("紅色代表人"));
 control_bar.add(new JLabel("藍色代表箱子"));
 control_bar.add(new JLabel("綠色代表終點"));
 restart.addActionListener(new ActionListener() {
 public void actionPerformed(ActionEvent e) {
 block[person.x][person.y].setBackground(Color.WHITE);
 person = (Point) start_of_person.clone();
 block[box.x][box.y].setBackground(Color.WHITE);
 box = (Point) start_of_box.clone();
 block[person.x][person.y].setBackground(Color.RED);
 block[box.x][box.y].setBackground(Color.BLUE);
 block[end.x][end.y].setBackground(Color.GREEN);
 passed_step = 0;
 show_cur_point.setText(" "+person.toString()+" ");
 updateStep();
 }
 });
 drawback.addActionListener(new ActionListener() {
 public void actionPerformed(ActionEvent e) {
 if (operation_recorder.empty())
  return;
 Operation cur_op = operation_recorder.peek();
 operation_recorder.pop();
 int dir;
 switch (cur_op.dir) {// 得到相反方向
 case 0:
  dir = 1;
  break;
 case 1:
  dir = 0;
  break;
 case 2:
  dir = 3;
  break;
 default:
  dir = 2;
 }
 // 推箱子的時候，箱子先走，人再走
 // 不推箱子的時候直接就是人走，所以棧頂元素始終是人的操作
 go(person, dir);// 人相反方向走一步
 show_cur_point.setText(" "+person.toString()+" ");
 if (!operation_recorder.empty()&&operation_recorder.peek().stuff == 1) {
  // 下一個是箱子，即人從該位置推動的箱子
  go(box, dir);// 箱子相反方向走一步
  operation_recorder.pop();
  --passed_step;
  updateStep();
 }
 }
 });
 PtbKeyAdapter ptbkeyadapter=new PtbKeyAdapter();
 start.addKeyListener(ptbkeyadapter);
 restart.addKeyListener(ptbkeyadapter);
 drawback.addKeyListener(ptbkeyadapter);
 start.setFont(font);
 restart.setFont(font);
 drawback.setFont(font);
 control_bar.add(start);
 control_bar.add(restart);
 control_bar.add(drawback);
 control_bar.setBounds(850, 100, 200, 600);
 this.paintMap();
 this.add(control_bar);
 }
 
 public void creatMap() {
 this.setLayout(null);
 this.map_area.removeAll();
 this.map_area.setVisible(false);
 paintMap();
 this.revalidate();
 this.map_area.setVisible(true);
 }
}

import java.util.*;
 
public class Map_Manager {
 private PTB_Map ptb_map = new PTB_Map();
 private int di[][] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
 private double search_limit;
 private int area[] = new int[4];
 private Map<Status, Boolean> visit_of_status = new HashMap<Status, Boolean>();
 private Map<Point, Integer> visit_of_box = new HashMap<Point, Integer>();
 private PriorityQueue<Status> q = new PriorityQueue<Status>(new Comparator<Status>() {
 public int compare(Status s1, Status s2) {
 return s1.step - s2.step;
 }
 });
 
 private class PTB_Map {
 private int width;
 private int height;
 private int step_of_map;
 private int accessible_point;
 private Point end_p = new Point();
 private Status start = new Status();
 private int matrix[][] = new int[100][100];
 private Map<Point, Point> path_map = new HashMap<Point, Point>();
 private Point[] path = new Point[1000];
 private double ratio_of_space;
 private double ratio_of_step;
 }
 
 public class Point implements Cloneable {
 int x, y;
 
 public boolean equals(Object obj) {
 if (!(obj instanceof Point))
 return false;
 Point point = (Point) obj;
 return this.x == point.x && this.y == point.y;
 }
 
 public int hashCode() {
 return this.x * ptb_map.width + this.y;
 }
 
 public Object clone() {
 Point newPoint = null;
 try {
 newPoint = (Point) super.clone();
 } catch (CloneNotSupportedException e) {
 e.printStackTrace();
 }
 return newPoint;
 }
 
 public String toString() {
 return "(" + (this.x + 1) + "," + (this.y + 1) + ")";
 }
 }
 
 private class Status implements Cloneable {
 Point box = new Point();
 Point person = new Point();
 int step;
 
 public int hashCode() {
 return this.box.hashCode() * this.person.hashCode() + this.step;
 }
 
 public boolean equals(Object obj) {
 if (!(obj instanceof Status))
 return false;
 Status status = (Status) obj;
 return this.box.equals(status.box) && this.person.equals(status.person) && this.step == status.step;
 }
 
 public Object clone() {
 Status newStatus = null;
 try {
 newStatus = (Status) super.clone();
 newStatus.box = (Point) box.clone();
 newStatus.person = (Point) person.clone();
 } catch (CloneNotSupportedException e) {
 e.printStackTrace();
 }
 return newStatus;
 }
 }
 
 public void setMap(int height, int width, double degree_of_difficulty) {
 this.ptb_map.height = height;
 this.ptb_map.width = width;
 this.ptb_map.ratio_of_space = 0.5;
 double ratio = 1;
 if (height + width < 20)
 ratio = 0.05 * (height + width);
 this.ptb_map.ratio_of_step = 0.5 + degree_of_difficulty * 0.05 * ratio;
 this.search_limit = (this.ptb_map.height * this.ptb_map.width) / 10;
 }
 
 public int getHeight() {
 return ptb_map.height;
 }
 
 public int getWidth() {
 return ptb_map.width;
 }
 
 public int getStepOfMap() {
 return ptb_map.step_of_map;
 }
 
 private boolean accessible(Point point) {// point可走則返回true
 if (point.x < 0 || point.x >= ptb_map.height || point.y < 0 || point.y >= ptb_map.width)// 越界
 return false;
 if (ptb_map.matrix[point.x][point.y] == 1)// 走到墻上
 return false;
 return true;
 }
 
 private void creatSpace(Point point) {
 Random random = new Random();
 int l = 0;
 while (l <= search_limit) {
 int dir = random.nextInt(4);
 if (point.x + di[dir][0] < 0 || point.x + di[dir][0] >= ptb_map.height || point.y + di[dir][1] < 0
  || point.y + di[dir][1] >= ptb_map.width)
 continue;// 若往該方向走一步越界，則換個方向
 point.x += di[dir][0];
 point.y += di[dir][1];
 if (this.ptb_map.matrix[point.x][point.y] != 0) {
 if (point.y < ptb_map.width / 2) {
  if (point.x < ptb_map.height / 2)
  ++area[0];// 該點在左上方
  else
  ++area[1];// 該點在左下方
 } else {
  if (point.x < ptb_map.height / 2)
  ++area[2];// 該點在右上方
  else
  ++area[3];// 該點在右下方
 }
 this.ptb_map.matrix[point.x][point.y] = 0;
 ++this.ptb_map.accessible_point;
 }
 ++l;
 }
 }
 
 private boolean produceMap() {// 返回值為地圖是否創(chuàng)建成功
 Random random = new Random();
 // 重置地圖的矩陣
 for (int i = 0; i < ptb_map.height; ++i)
 for (int j = 0; j < ptb_map.width; ++j)
 ptb_map.matrix[i][j] = 1;
 do// 隨機設(shè)置人和箱子的初始位置
 {
 ptb_map.start.box.x = random.nextInt(ptb_map.height);
 ptb_map.start.box.y = random.nextInt(ptb_map.width);
 ptb_map.start.person.x = random.nextInt(ptb_map.height);
 ptb_map.start.person.y = random.nextInt(ptb_map.width);
 } while (ptb_map.start.box.equals(ptb_map.start.person));
 ptb_map.accessible_point = 0;
 ptb_map.matrix[ptb_map.start.person.x][ptb_map.start.person.x] = 0;
 // 設(shè)置一定的墻
 ptb_map.accessible_point = 0;
 Point start = (Point) ptb_map.start.person.clone();// 最開始走的位置為人的初始位置
 area[0] = area[1] = area[2] = area[3] = 0;
 creatSpace(start);
 while (ptb_map.accessible_point < (ptb_map.height * ptb_map.width) * ptb_map.ratio_of_space) {
 int min = 10000, min_area = 0;
 for (int i = 0; i < 4; ++i)
 if (area[i] < min) {
  min = area[i];
  min_area = i;
 }
 switch (min_area) {
 case 0:// 左上
 start.x = random.nextInt(ptb_map.height / 2);
 start.y = random.nextInt(ptb_map.width / 2);
 break;
 case 1:// 左下
 start.x = random.nextInt(ptb_map.height / 2) + ptb_map.height / 2;
 start.y = random.nextInt(ptb_map.width / 2);
 break;
 case 2:// 右上
 start.x = random.nextInt(ptb_map.height / 2);
 start.y = random.nextInt(ptb_map.width / 2) + ptb_map.width / 2;
 break;
 case 3:// 右下
 start.x = random.nextInt(ptb_map.height / 2) + ptb_map.height / 2;
 start.y = random.nextInt(ptb_map.width / 2) + ptb_map.width / 2;
 break;
 }
 creatSpace(start);
 }
 ptb_map.end_p = (Point) start.clone();
 ptb_map.matrix[ptb_map.start.person.x][ptb_map.start.person.y] = 4;
 ptb_map.matrix[ptb_map.start.box.x][ptb_map.start.box.y] = 2;
 ptb_map.matrix[ptb_map.end_p.x][ptb_map.end_p.y] = 3;
 return true;
 }
 
 private boolean solveMap() {// 返回值為當前地圖是否有路徑
 q.clear();
 visit_of_box.clear();
 ptb_map.path_map.clear();
 ptb_map.step_of_map = 0;
 ptb_map.start.step = 0;
 int pre_step = -1;
 q.add(ptb_map.start);
 visit_of_status.put(ptb_map.start, true);
 while (!q.isEmpty()) {
 Status pre_Status = (Status) q.peek().clone();
 if (pre_Status.step != pre_step) {
 visit_of_status.clear();
 pre_step = pre_Status.step;
 }
 for (int i = 0; i < 4; ++i) {
 Status cur_Status = (Status) pre_Status.clone();
 cur_Status.person.x += di[i][0];
 cur_Status.person.y += di[i][1];
 if (!accessible(cur_Status.person))// 該點不可走
  continue;
 if (visit_of_status.containsKey(cur_Status))// 該點已經(jīng)走過
  continue;
 // 保存當前點的前一個,用于輸出路徑
 if (cur_Status.person.equals(cur_Status.box))// 走到箱子上
 {
  Point next_box = new Point();// 當前人會把箱子推到的位置
  next_box.x = cur_Status.box.x + di[i][0];
  next_box.y = cur_Status.box.y + di[i][1];
  if (!accessible(next_box))// 該點不可走
  continue;
  if (ptb_map.path_map.containsKey(next_box))
  continue;
  if (visit_of_box.containsKey(next_box)) {
  if (visit_of_box.get(next_box) > 4)// 當前位置箱子已走過四次
  continue;
  }
  // 箱子可以走到該點，則箱子走一步
  ptb_map.path_map.put(next_box, cur_Status.box);
  cur_Status.box = next_box;
  ++cur_Status.step;
  if (!visit_of_box.containsKey(cur_Status.box))
  visit_of_box.put(cur_Status.box, 1);
  else {
  int t = visit_of_box.get(cur_Status.box);
  ++t;
  visit_of_box.put(cur_Status.box, t);
  }
  if (cur_Status.box.equals(ptb_map.end_p))// 箱子走到終點
  {
  ptb_map.step_of_map = cur_Status.step;
  q.clear();
  if (ptb_map.step_of_map < (ptb_map.height + ptb_map.width) * ptb_map.ratio_of_step)
  return false;
  else
  return true;
  }
 }
 q.add(cur_Status);
 visit_of_status.put(cur_Status, true);
 }
 pre_Status = null;
 q.poll();
 }
 return false;
 }
 
 public void recordPath() {// 記錄路徑
 Stack<Point> output_path = new Stack<Point>();// 用于輸出路徑
 Point cur_point = (Point) ptb_map.end_p.clone();// 從終點開始
 int step = -1;
 while (step != ptb_map.step_of_map) {
 ++step;
 output_path.push(cur_point);
 cur_point = ptb_map.path_map.get(cur_point);
 if (cur_point == null)
 break;
 }
 int i = 0;
 while (!output_path.empty())// 將路徑保存在點數(shù)組里
 {
 ptb_map.path[i] = output_path.peek();
 output_path.pop();
 ++i;
 }
 }
 
 public void creatMap() {
 int i = 0;
 do {
 while (!produceMap())
 ;
 ++i;
 } while (!solveMap());
 recordPath();
 printMap();//
 System.out.println(i);//
 }
 
 public int[][] getMap() {
 return ptb_map.matrix;
 }
 
 public Point getStartBoxPoint() {
 return ptb_map.start.box;
 }
 
 public Point getStartPersonPoint() {
 return ptb_map.start.person;
 }
 
 public Point getEndPoint() {
 return ptb_map.end_p;
 }
 
 private void printMap() {
 for (int i = 0; i < ptb_map.height; ++i) {
 System.out.print(ptb_map.matrix[i][0]);
 for (int j = 1; j < ptb_map.width; ++j)
 System.out.print(" " + ptb_map.matrix[i][j]);
 System.out.println();
 }
 }
 
 public Point[] getPath() {
 return ptb_map.path;
 }
}