import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.Toolkit;
import java.awt.datatransfer.StringSelection;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.util.ArrayList;
import java.util.Formatter;
import java.util.List;
import java.util.Random;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.WindowConstants;

/**
 * メインクラス
 */
public class Main {

	/**
	 * 1体の敵
	 */
	static class Enemy {

		/**
		 * 敵の種別
		 */
		enum Kind {
			/**
			 * 敵V
			 */
			V,
			/**
			 * 敵H
			 */
			H,
			/**
			 * 敵L
			 */
			L,
			/**
			 * 敵R
			 */
			R,
			/**
			 * 敵Jが敵Lになっている状態
			 */
			JL,
			/**
			 * 敵Jが敵Rになっている状態
			 */
			JR,
		}

		/**
		 * X座標
		 */
		int x;
		/**
		 * Y座標
		 */
		int y;
		/**
		 * 直前のX座標
		 */
		int lastX;
		/**
		 * 直前のY座標
		 */
		int lastY;
		/**
		 * 種類
		 */
		Kind kind;

		/**
		 * 敵を初期化
		 * @param x X座標
		 * @param y Y座標
		 * @param kind 種類
		 */
		Enemy(final int x, final int y, final Kind kind) {
			this.x = x;
			this.y = y;
			this.lastX = x;
			this.lastY = y;
			this.kind = kind;
		}

		/**
		 * 移動
		 * @param data データ
		 * @param player プレイヤ
		 * @param time 時刻
		 */
		void move(final char[][] data, final Player player, final AtomicInteger time) {
			final char down = data[this.y + 1][this.x];
			final char left = data[this.y][this.x - 1];
			final char up = data[this.y - 1][this.x];
			final char right = data[this.y][this.x + 1];
			if (time.get() == 0) {
				/*
				 * 時刻 t = 0 においては、初期位置の 下、左、上、右 の順で最初に進入可能なマスの方向に移動します。
				 */
				if (down != '#') {
					this.y++;
				} else if (left != '#') {
					this.x--;
				} else if (up != '#') {
					this.y--;
				} else if (right != '#') {
					this.x++;
				} else {
					System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n", time.get(),
							this.x, this.y, this.kind);
				}
			} else {
				final int numOfWalls = (down == '#' ? 1 : 0) + (left == '#' ? 1 : 0)
						+ (up == '#' ? 1 : 0) + (right == '#' ? 1 : 0);
				if (numOfWalls == 3) {
					/*
					 * 行き止まりマスの場合、唯一進入可能な隣接マスに移動します。
					 */
					if (down != '#') {
						this.y++;
					} else if (left != '#') {
						this.x--;
					} else if (up != '#') {
						this.y--;
					} else if (right != '#') {
						this.x++;
					} else {
						System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n", time.get(),
								this.x, this.y, this.kind);
					}
				} else if (numOfWalls == 2) {
					/*
					 * 通路マスの場合、時刻 t-1 に居たマス以外の進入可能な隣接するマスに移動します。
					 */
					if (down != '#' && this.lastY != this.y + 1) {
						this.y++;
					} else if (left != '#' && this.lastX != this.x - 1) {
						this.x--;
					} else if (up != '#' && this.lastY != this.y - 1) {
						this.y--;
					} else if (right != '#' && this.lastX != this.x + 1) {
						this.x++;
					} else {
						System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n", time.get(),
								this.x, this.y, this.kind);
					}
				} else if (numOfWalls == 1 || numOfWalls == 0) {
					/*
					 * 交差点マスの場合は、敵の種別に応じたアルゴリズムに応じて移動方向を決定します。
					 */
					final int dX = player.lastX - this.x;
					final int dY = player.lastY - this.y;
					final int signDX = (int) Math.signum(dX);
					final int signDY = (int) Math.signum(dY);
					switch (this.kind) {
					case V:
						/*
						 * 敵から見た自機の相対位置を (dx, dy) と表すものとします。次のルールを上から順に適用し、最初に選ばれた方向に移動します。
						 * 1. dy ≠ 0 でかつ dy の符号方向にあるマスが進入可能であれば、その方向に移動します。
						 * 2. dx ≠ 0 でかつ dx の符号方向にあるマスが進入可能であれば、その方向に移動します。
						 * 3. 現在位置の 下、左、上、右 の順で最初に進入可能なマスの方向に移動する。
						 */
						if (dY != 0 && data[this.y + signDY][this.x] != '#') {
							this.y += signDY;
						} else if (dX != 0 && data[this.y][this.x + signDX] != '#') {
							this.x += signDX;
						} else {
							if (down != '#') {
								this.y++;
							} else if (left != '#') {
								this.x--;
							} else if (right != '#') {
								this.x++;
							} else if (up != '#') {
								this.y--;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						}
						break;
					case H:
						/*
						 * 敵 V とほぼ同じです。唯一異なるのは 、進行方向を決めるルールのうち、
						 * 最初の二つのルールの適用順序が入れ替わるところです。
						 * すなわち、先に dx ≠ 0 のチェックを行ない、次に dy ≠ 0 のチェックを行います。
						 */
						if (dX != 0 && data[this.y][this.x + signDX] != '#') {
							this.x += signDX;
						} else if (dY != 0 && data[this.y + signDY][this.x] != '#') {
							this.y += signDY;
						} else {
							if (down != '#') {
								this.y++;
							} else if (left != '#') {
								this.x--;
							} else if (right != '#') {
								this.x++;
							} else if (up != '#') {
								this.y--;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						}
						break;
					case L:
					case JL:
						/*
						 * 現在位置への進入方向から見て相対的に 左、前、右 の順で最初に進入可能なマスの方向に移動します。
						 */
						if (this.lastY + 1 == this.y) {
							if (right != '#') {
								this.x++;
							} else if (down != '#') {
								this.y++;
							} else if (left != '#') {
								this.x--;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						} else if (this.lastX - 1 == this.x) {
							if (down != '#') {
								this.y++;
							} else if (left != '#') {
								this.x--;
							} else if (up != '#') {
								this.y--;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						} else if (this.lastY - 1 == this.y) {
							if (left != '#') {
								this.x--;
							} else if (up != '#') {
								this.y--;
							} else if (right != '#') {
								this.x++;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						} else if (this.lastX + 1 == this.x) {
							if (up != '#') {
								this.y--;
							} else if (right != '#') {
								this.x++;
							} else if (down != '#') {
								this.y++;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						} else {
							System.err.printf("止まっていた？t = %d, x = %d, y = %d, kind = %s\n",
									time.get(), this.x, this.y, this.kind);
						}
						break;
					case R:
					case JR:
						/*
						 * 現在位置への進入方向から見て相対的に 右、前、左 の順で最初に進入可能なマスの方向に移動します。
						 */
						if (this.lastY + 1 == this.y) {
							if (left != '#') {
								this.x--;
							} else if (down != '#') {
								this.y++;
							} else if (right != '#') {
								this.x++;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						} else if (this.lastX - 1 == this.x) {
							if (up != '#') {
								this.y--;
							} else if (left != '#') {
								this.x--;
							} else if (down != '#') {
								this.y++;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						} else if (this.lastY - 1 == this.y) {
							if (right != '#') {
								this.x++;
							} else if (up != '#') {
								this.y--;
							} else if (left != '#') {
								this.x--;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						} else if (this.lastX + 1 == this.x) {
							if (down != '#') {
								this.y++;
							} else if (right != '#') {
								this.x++;
							} else if (up != '#') {
								this.y--;
							} else {
								System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n",
										time.get(), this.x, this.y, this.kind);
							}
						} else {
							System.err.printf("止まっていた？t = %d, x = %d, y = %d, kind = %s\n",
									time.get(), this.x, this.y, this.kind);
						}
						break;
					}
					/*
					 * 交差点マスに入るたびに、最初は敵Lの行動、次回は敵Rの行動、さらに次回はまた敵Lの行動、と繰り返します。
					 */
					this.kind = this.kind == Kind.JL ? Kind.JR : (this.kind == Kind.JR ? Kind.JL
							: this.kind);
				} else {
					System.err.printf("動けません。t = %d, x = %d, y = %d, kind = %s\n", time.get(),
							this.x, this.y, this.kind);
				}
			}
		}

		/**
		 * @param player プレイヤ
		 * @return 殺したかどうか
		 */
		boolean killed(final Player player) {
			if (this.x == player.x && this.y == player.y) {
				return true;
			} else if (this.x == player.lastX && this.y == player.lastY && this.lastX == player.x
					&& this.lastY == player.y) {
				return true;
			} else {
				return false;
			}
		}

		@Override
		public String toString() {
			return new Formatter().format("[x = %d, y = %d, kind = %s]", this.x, this.y, this.kind)
					.toString();
		}
	}

	/**
	 * プレイヤ
	 */
	static class Player {
		/**
		 * X座標
		 */
		int x = -1;
		/**
		 * Y座標
		 */
		int y = -1;
		/**
		 * 直前のX座標
		 */
		int lastX = -1;
		/**
		 * 直前のY座標
		 */
		int lastY = -1;

		/**
		 * 上へ移動
		 * @param data データ
		 * @param log ログ
		 */
		void moveDown(final char[][] data, final StringBuilder log) {
			this.lastX = this.x;
			this.lastY = this.y;
			if (data[this.y + 1][this.x] != '#') {
				this.y++;
			}
			log.append('j');
		}

		/**
		 * 左へ移動
		 * @param data データ
		 * @param log ログ
		 */
		void moveLeft(final char[][] data, final StringBuilder log) {
			this.lastX = this.x;
			this.lastY = this.y;
			if (data[this.y][this.x - 1] != '#') {
				this.x--;
			}
			log.append('h');
		}

		/**
		 * 上へ移動
		 * @param data データ
		 * @param log ログ
		 */
		void moveUp(final char[][] data, final StringBuilder log) {
			this.lastX = this.x;
			this.lastY = this.y;
			if (data[this.y - 1][this.x] != '#') {
				this.y--;
			}
			log.append('k');
		}

		/**
		 * 右へ移動
		 * @param data データ
		 * @param log ログ
		 */
		void moveRight(final char[][] data, final StringBuilder log) {
			this.lastX = this.x;
			this.lastY = this.y;
			if (data[this.y][this.x + 1] != '#') {
				this.x++;
			}
			log.append('l');
		}

		/**
		 * 留まる
		 * @param log ログ
		 */
		void stay(final StringBuilder log) {
			this.lastX = this.x;
			this.lastY = this.y;
			log.append('.');
		}

		@Override
		public String toString() {
			return new Formatter().format("[x = %d, y = %d, lX = %d, lY = %d]", this.x, this.y,
					this.lastX, this.lastY).toString();
		}
	}

	/**
	 * ステージ
	 */
	enum Stage {
		/**
		 * 入力1
		 */
		LV1(50, 11, 7, "###########" + "#.V..#..H.#" + "#.##...##.#" + "#L#..#..R.#"
				+ "#.#.###.#.#" + "#....@....#" + "###########"),
		/**
		 * 入力2
		 */
		LV2(300, 20, 17, "####################" + "###.....L..........#" + "###.##.##.##L##.##.#"
				+ "###.##.##.##.##.##.#" + "#.L................#" + "#.##.##.##.##.##.###"
				+ "#.##.##L##.##.##.###" + "#.................L#" + "#.#.#.#J####J#.#.#.#"
				+ "#L.................#" + "###.##.##.##.##.##.#" + "###.##.##R##.##.##.#"
				+ "#................R.#" + "#.##.##.##.##R##.###" + "#.##.##.##.##.##.###"
				+ "#@....R..........###" + "####################"),
		/**
		 * 入力3
		 */
		LV3(700, 58, 17, "##########################################################"
				+ "#........................................................#"
				+ "#.###.#########.###############.########.###.#####.#####.#"
				+ "#.###.#########.###############.########.###.#####.#####.#"
				+ "#.....#########....J.............J.......###.............#"
				+ "#####.###.......#######.#######.########.###.#######.#####"
				+ "#####.###.#####J#######.#######.########.###.##   ##.#####"
				+ "#####.###L#####.##   ##L##   ##.##    ##.###.##   ##.#####"
				+ "#####.###..H###.##   ##.##   ##.########.###.#######J#####"
				+ "#####.#########.##   ##L##   ##.########.###.###V....#####"
				+ "#####.#########.#######.#######..........###.#######.#####"
				+ "#####.#########.#######.#######.########.###.#######.#####"
				+ "#.....................L.........########..........R......#"
				+ "#L####.##########.##.##########....##....#########.#####.#"
				+ "#.####.##########.##.##########.##.##.##.#########.#####.#"
				+ "#.................##............##..@.##...............R.#"
				+ "##########################################################");
		/**
		 * 制限時間
		 */
		int timeLimit;
		/**
		 * 幅
		 */
		int width;
		/**
		 * 高さ
		 */
		int height;
		/**
		 * データ
		 */
		char[][] data;
		/**
		 * 点
		 */
		int dots;

		/**
		 * ステージを初期化
		 * @param timeLimit 制限時間
		 * @param width 幅
		 * @param height 高さ
		 * @param string 入力文字列
		 */
		Stage(final int timeLimit, final int width, final int height, final String string) {
			this.timeLimit = timeLimit;
			this.width = width;
			this.height = height;
			this.data = new char[height][width];
			this.dots = 0;
			for (int i = 0; i < height; i++) {
				for (int j = 0; j < width; j++) {
					final char character = string.charAt(i * width + j);
					this.data[i][j] = character;
					if (character == '.') {
						this.dots++;
					}
				}
			}
		};
	}

	/**
	 * メインメソッド
	 * @param args コマンドライン引数
	 * @throws InterruptedException 割り込み例外
	 */
	public static void main(final String[] args) throws InterruptedException {
		final Stage stage = Stage.LV1;
		final int timeLimit = stage.timeLimit;
		final int width = stage.width;
		final int height = stage.height;
		final char[][] data = new char[height][width];
		final Player player = new Player();
		final List<Enemy> enemies = new ArrayList<Enemy>();
		final AtomicInteger time = new AtomicInteger();
		final AtomicInteger dots = new AtomicInteger();
		final StringBuilder log = new StringBuilder();
		final AtomicBoolean isDead = new AtomicBoolean();
		final JFrame frame = new JFrame(stage.toString());
		final int size = 20;
		final JLabel statusLabel = new JLabel("ここに現在の状態が表示されます。");
		statusLabel.setOpaque(true);
		statusLabel.setBackground(Color.WHITE);
		frame.add(statusLabel, BorderLayout.NORTH);
		final JPanel playPanel = new JPanel() {
			@Override
			protected void paintComponent(final Graphics graphics) {
				super.paintComponent(graphics);
				final Graphics2D g = (Graphics2D) graphics;
				g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
						RenderingHints.VALUE_ANTIALIAS_ON);
				g.setColor(Color.RED);
				g.fillOval(player.x * size, player.y * size, size, size);
				for (final Enemy enemy : enemies) {
					switch (enemy.kind) {
					case V:
						g.setColor(Color.GREEN);
						break;
					case H:
						g.setColor(Color.BLUE);
						break;
					case L:
						g.setColor(Color.ORANGE);
						break;
					case R:
						g.setColor(Color.PINK);
						break;
					case JL:
					case JR:
						g.setColor(Color.CYAN);
						break;
					default:
						g.setColor(Color.BLACK);
					}
					g.fillOval(enemy.x * size, enemy.y * size, size, size);
				}
				g.setColor(Color.BLACK);
				for (final Enemy enemy : enemies) {
					g.drawString(enemy.kind.toString(), enemy.x * size + size / 2
							- g.getFontMetrics().stringWidth(enemy.kind.toString()) / 2, enemy.y
							* size + g.getFontMetrics().getAscent());
				}
				g.drawString("P", player.x * size + size / 2 - g.getFontMetrics().stringWidth("P")
						/ 2, player.y * size + g.getFontMetrics().getAscent());
				for (int i = 0; i < height; i++) {
					for (int j = 0; j < width; j++) {
						switch (data[i][j]) {
						case '#':
							g.setColor(Color.GRAY);
							g.fillRect(j * size, i * size, size, size);
							break;
						case '.':
							g.setColor(Color.BLACK);
							g.fillOval(j * size + size / 2 - 2, i * size + size / 2 - 2, 4, 4);
							break;
						}
					}
				}
			}
		};
		playPanel.setFocusable(true);
		playPanel.addKeyListener(new KeyAdapter() {
			@Override
			public void keyPressed(final KeyEvent e) {
				switch (e.getKeyCode()) {
				case KeyEvent.VK_ESCAPE:
					initialize(width, height, data, stage, player, enemies, time, dots, log,
							isDead, statusLabel, timeLimit);
					playPanel.repaint();
					break;
				case KeyEvent.VK_Z:
					playBack(log.toString().replaceFirst(".$", ""), stage, timeLimit, width,
							height, data, player, enemies, time, dots, log, isDead, statusLabel,
							playPanel);
					playPanel.repaint();
					updateStatusLabel(statusLabel, stage, timeLimit, time, dots, log);
					break;
				case KeyEvent.VK_1:
					break;
				case KeyEvent.VK_2:
					break;
				case KeyEvent.VK_3:
				}
				if (!isDead.get()) {
					switch (e.getKeyCode()) {
					case KeyEvent.VK_DOWN:
					case KeyEvent.VK_J:
						player.moveDown(data, log);
						break;
					case KeyEvent.VK_LEFT:
					case KeyEvent.VK_H:
						player.moveLeft(data, log);
						break;
					case KeyEvent.VK_UP:
					case KeyEvent.VK_K:
						player.moveUp(data, log);
						break;
					case KeyEvent.VK_RIGHT:
					case KeyEvent.VK_L:
						player.moveRight(data, log);
						break;
					case KeyEvent.VK_SPACE:
					case KeyEvent.VK_ENTER:
					case KeyEvent.VK_PERIOD:
						player.stay(log);
						break;
					default:
						return;
					}
					moveEnemies(data, player, enemies, time, isDead);
					getDot(data, player, dots);
					time.incrementAndGet();
					if (time.get() >= timeLimit) {
						isDead.set(true);
					}
					if (dots.get() == stage.dots) {
						System.out.printf("(cleared)time: %d/%d, score: %d/%d, log: %s\n",
								time.get(), timeLimit, dots.get(), stage.dots, log);
						isDead.set(true);
					}
					playPanel.repaint();
					updateStatusLabel(statusLabel, stage, timeLimit, time, dots, log);
					if (isDead.get()) {
						statusLabel.setText((dots.get() == stage.dots ? "(cleared)" : "(dead)")
								+ statusLabel.getText());
						Toolkit.getDefaultToolkit().getSystemClipboard()
								.setContents(new StringSelection(log.toString()), null);
					}
				}
			}
		});
		playPanel.setPreferredSize(new Dimension(width * size, height * size));
		playPanel.setBackground(Color.WHITE);
		frame.add(playPanel);
		frame.pack();
		frame.setLocationByPlatform(true);
		frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
		initialize(width, height, data, stage, player, enemies, time, dots, log, isDead,
				statusLabel, timeLimit);
		final boolean isGUI = false;
		frame.setVisible(isGUI);
		if (isGUI) {
			Thread.sleep(1000);
		}
		final Random random = new Random();
		int maxDots = 0;
		int maxTime = 0;
		double resetRate = .001;
		final double stayRate = .2;
		final double forwardRate = .9;
		final double hungryRate = .8;
		String rollBackPoint = "";
		while (true) {
			if (random.nextDouble() < stayRate) {
				player.stay(log);
			} else {
				final char down = data[player.y + 1][player.x];
				final char left = data[player.y][player.x - 1];
				final char up = data[player.y - 1][player.x];
				final char right = data[player.y][player.x + 1];
				final int numOfWalls = (down == '#' ? 1 : 0) + (left == '#' ? 1 : 0)
						+ (up == '#' ? 1 : 0) + (right == '#' ? 1 : 0);
				if (numOfWalls < 2) {
					rollBackPoint = log.toString();
				}
				final int numOfDots = (down == '.' ? 1 : 0) + (left == '.' ? 1 : 0)
						+ (up == '.' ? 1 : 0) + (right == '.' ? 1 : 0);
				if (numOfDots > 0 && random.nextDouble() < hungryRate) {
					loop: while (true) {
						switch (random.nextInt(4)) {
						case 0:
							if (down == '.') {
								player.moveDown(data, log);
								break loop;
							}
							break;
						case 1:
							if (left == '.') {
								player.moveLeft(data, log);
								break loop;
							}
							break;
						case 2:
							if (up == '.') {
								player.moveUp(data, log);
								break loop;
							}
							break;
						case 3:
							if (right == '.') {
								player.moveRight(data, log);
								break loop;
							}
							break;
						}
					}
				} else {
					loop: while (true) {
						final boolean isForward = random.nextDouble() < forwardRate;
						switch (random.nextInt(4)) {
						case 0:
							if (down != '#') {
								if (isForward && player.lastY == player.y + 1) {
									break;
								}
								player.moveDown(data, log);
								break loop;
							}
							break;
						case 1:
							if (left != '#') {
								if (isForward && player.lastX == player.x - 1) {
									break;
								}
								player.moveLeft(data, log);
								break loop;
							}
							break;
						case 2:
							if (up != '#') {
								if (isForward && player.lastY == player.y - 1) {
									break;
								}
								player.moveUp(data, log);
								break loop;
							}
							break;
						case 3:
							if (right != '#') {
								if (isForward && player.lastX == player.x + 1) {
									break;
								}
								player.moveRight(data, log);
								break loop;
							}
							break;
						}
					}
				}
			}
			moveEnemies(data, player, enemies, time, isDead);
			getDot(data, player, dots);
			time.incrementAndGet();
			if (time.get() >= timeLimit) {
				isDead.set(true);
			}
			if (dots.get() == stage.dots) {
				isDead.set(true);
			}
			if (isDead.get()) {
				if (dots.get() > maxDots) {
					System.out.printf("time: %d/%d, score: %d/%d, log: %s\n", time.get(),
							timeLimit, dots.get(), stage.dots, log);
					maxDots = dots.get();
				}
				if (dots.get() == stage.dots && timeLimit - time.get() > maxTime) {
					System.out.printf("clear! time: %d, score: %d, log: %s\n",
							timeLimit - time.get(), dots.get(), log);
					maxTime = timeLimit - time.get();
				}
				if (random.nextDouble() < resetRate) {
					initialize(width, height, data, stage, player, enemies, time, dots, log,
							isDead, statusLabel, timeLimit);
					resetRate *= .9;
				} else {
					if (random.nextBoolean()) {
						playBack(log.subSequence(0, log.length() * 99 / 100).toString(), stage,
								timeLimit, width, height, data, player, enemies, time, dots, log,
								isDead, statusLabel, playPanel);
					} else {
						playBack(rollBackPoint, stage, timeLimit, width, height, data, player,
								enemies, time, dots, log, isDead, statusLabel, playPanel);
					}
				}

			}
			if (isGUI) {
				playPanel.repaint();
				statusLabel.setText(new Formatter().format("time: %d, score: %d, log: %s",
						timeLimit - time.get(), dots.get(), log).toString());
				Thread.sleep(10);
			}
		}
	}

	/**
	 * 初期化
	 * @param width 幅
	 * @param height 高さ
	 * @param data データ
	 * @param stage ステージ
	 * @param player プレイヤ
	 * @param enemies 敵
	 * @param time 時刻
	 * @param dots 点
	 * @param log ログ
	 * @param isDead 死んでいるかどうか
	 * @param statusLabel ラベル
	 * @param timeLimit 制限時間
	 */
	static void initialize(final int width, final int height, final char[][] data,
			final Stage stage, final Player player, final List<Enemy> enemies,
			final AtomicInteger time, final AtomicInteger dots, final StringBuilder log,
			final AtomicBoolean isDead, final JLabel statusLabel, final int timeLimit) {
		enemies.clear();
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				final char kind = stage.data[i][j];
				switch (kind) {
				case 'V':
					data[i][j] = ' ';
					enemies.add(new Enemy(j, i, Enemy.Kind.V));
					break;
				case 'H':
					data[i][j] = ' ';
					enemies.add(new Enemy(j, i, Enemy.Kind.H));
					break;
				case 'L':
					data[i][j] = ' ';
					enemies.add(new Enemy(j, i, Enemy.Kind.L));
					break;
				case 'R':
					data[i][j] = ' ';
					enemies.add(new Enemy(j, i, Enemy.Kind.R));
					break;
				case 'J':
					data[i][j] = ' ';
					enemies.add(new Enemy(j, i, Enemy.Kind.JL));
					break;
				case '@':
					data[i][j] = ' ';
					player.x = j;
					player.y = i;
					player.lastX = player.x;
					player.lastY = player.y;
					break;
				case '#':
				case '.':
				case ' ':
					data[i][j] = stage.data[i][j];
					break;
				default:
					System.err.printf("unknown data: '%s', x = %d, y = %d\n", stage.data[i][j], j,
							i);
				}
			}
		}
		time.set(0);
		dots.set(0);
		log.setLength(0);
		isDead.set(false);
		updateStatusLabel(statusLabel, stage, timeLimit, time, dots, log);
	}

	/**
	 * リプレイ
	 * @param string 動作を指示する文字列
	 * @param stage ステージ
	 * @param timeLimit 制限時間
	 * @param width 幅
	 * @param height 高さ
	 * @param data データ
	 * @param player プレイヤ
	 * @param enemies 敵
	 * @param time 時刻
	 * @param dots 点
	 * @param log ログ
	 * @param isDead 死んでいるかどうか
	 * @param statusLabel ラベル
	 * @param playPanel パネル
	 */
	static void playBack(final String string, final Stage stage, final int timeLimit,
			final int width, final int height, final char[][] data, final Player player,
			final List<Enemy> enemies, final AtomicInteger time, final AtomicInteger dots,
			final StringBuilder log, final AtomicBoolean isDead, final JLabel statusLabel,
			final JPanel playPanel) {
		initialize(width, height, data, stage, player, enemies, time, dots, log, isDead,
				statusLabel, timeLimit);
		for (int i = 0; i < string.length(); i++) {
			if (!isDead.get()) {
				switch (string.charAt(i)) {
				case 'j':
					player.moveDown(data, log);
					break;
				case 'h':
					player.moveLeft(data, log);
					break;
				case 'k':
					player.moveUp(data, log);
					break;
				case 'l':
					player.moveRight(data, log);
					break;
				case '.':
					player.stay(log);
					break;
				default:
					System.err.printf("unknown data: %s\n", string.charAt(i));
				}
				moveEnemies(data, player, enemies, time, isDead);
				getDot(data, player, dots);
				time.incrementAndGet();
				if (time.get() >= timeLimit) {
					isDead.set(true);
				}
			}
		}
	}

	/**
	 * 点を食べる
	 * @param data データ
	 * @param player プレイヤ
	 * @param dots 点
	 */
	static void getDot(final char[][] data, final Player player, final AtomicInteger dots) {
		if (data[player.y][player.x] == '.') {
			data[player.y][player.x] = ' ';
			dots.incrementAndGet();
		}
	}

	/**
	 * 敵を移動
	 * @param data データ
	 * @param player プレイヤ
	 * @param enemies 敵
	 * @param time 時刻
	 * @param isDead 死んでいるかどうか
	 */
	static void moveEnemies(final char[][] data, final Player player, final List<Enemy> enemies,
			final AtomicInteger time, final AtomicBoolean isDead) {
		for (final Enemy enemy : enemies) {
			final int x = enemy.x;
			final int y = enemy.y;
			enemy.move(data, player, time);
			enemy.lastX = x;
			enemy.lastY = y;
			if (enemy.killed(player)) {
				isDead.set(true);
			}
		}
	}

	/**
	 * 現在の状態を表示するラベルを更新
	 * @param statusLabel ラベル
	 * @param stage ステージ
	 * @param timeLimit 制限時間
	 * @param time 時刻
	 * @param dots 点
	 * @param log ログ
	 */
	static void updateStatusLabel(final JLabel statusLabel, final Stage stage, final int timeLimit,
			final AtomicInteger time, final AtomicInteger dots, final StringBuilder log) {
		statusLabel.setText(new Formatter().format("time: %d/%d, score: %d/%d, log: %s",
				time.get(), timeLimit, dots.get(), stage.dots, log).toString());
	}
}