import java.util.Vector;

public class SokobanLevel {
	public static final int EMPTY = 1;
	public static final int TARGET = 2;
	public static final int BOX = 4;
	public static final int PLAYER = 8;

	private int width;
	private int height;
	private int cells[][];
	private int working[][];

	/**
	 * Current x-position of the player.
	 */
	private int playerX;

	/**
	 * Current y-position of the player.
	 */
	private int playerY;

	/**
	 * Start x-position of the player.
	 */
	private int playerXStart;

	/**
	 * Start y-position of the player.
	 */
	private int playerYStart;

	/**
	 * Move history. Stores the destination position as an Integer (x + width * y).
	 */
	private Vector moves;

	/**
	 * Box moved history. If a box was moved, true is stored as an Boolean.
	 */
	private Vector boxMoved;

	/**
	 * Number of boxes.
	 */
	private int boxCount;

	/**
	 * Number of boxes on target fields.
	 */
	private int targetCount;

	/**
	 * Creates a new level.
	 * @param width Width of the level (without border-wall).
	 * @param height Height of the level (without border-wall).
	 * @param data One item is a string and represents one row the level.
	 */
	public SokobanLevel(int w, int h, Vector data) {
		width = w + 2;
		height = h + 2;
		cells = new int[width][height];
		boxCount = 0;
		targetCount = 0;
		playerXStart = -1;
		for (int y = 0; y < height; y++) {
			String row = null;
			if (y > 0 && y < height - 1)
				row = (String) data.elementAt(y - 1);
			for (int x = 0; x < width; x++) {
				cells[x][y] = 0;
				if (row != null
					&& x > 0
					&& x < width - 1
					&& row.length() > x - 1) {
					int b = row.charAt(x - 1);
					if (b != ' ') {
						if (b == '0')
							b = 10;
						else
							b = b - '0';
						if (y != 0
							&& y != height - 1
							&& x != 0
							&& x != width - 1
							&& b != ' ') {
							int r = 0;
							if ((b & EMPTY) > 0)
								r |= EMPTY;
							if ((b & TARGET) > 0) {
								targetCount++;
								r |= TARGET;
							}
							if ((b & BOX) > 0) {
								boxCount++;
								r |= BOX;
							}
							if ((b & PLAYER) > 0) {
								playerXStart = x;
								playerYStart = y;
							}
							cells[x][y] = r;
						}
					}
				}
			}
		}
		working = new int[width][height];
		restart();
	}

	/**
	 * Restarts the level.
	 */
	public void restart() {
		// copy the level to the working area
		targetCount = 0;
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				working[x][y] = cells[x][y];
				if (cells[x][y] == (BOX | TARGET))
					targetCount++;
			}
		}

		// reset the move and the box-flag history
		moves = new Vector();
		boxMoved = new Vector();
		playerX = playerXStart;
		playerY = playerYStart;
	}

	/**
	 * Moves the player.
	 */
	public boolean move(int dx, int dy) {
		int b;
		boolean move = false;
		int fromX = playerX + dx;
		int fromY = playerY + dy;
		b = working[fromX][fromY];
		if ((b & BOX) == 0) {
			if ((b & EMPTY) > 0 || (b & TARGET) > 0) {
				// set the move flag
				move = true;

				// historize a 'false' to indicate that the box was not moved
				boxMoved.addElement(new Boolean(false));
			}
		} else {
			int toX = playerX + 2 * dx;
			int toY = playerY + 2 * dy;
			b = working[toX][toY];
			if (b == EMPTY || b == TARGET) {
				// move the box
				working[fromX][fromY] ^= BOX;
				working[toX][toY] |= BOX;
				if ((working[fromX][fromY] & TARGET) > 0)
					targetCount--;
				if ((working[toX][toY] & TARGET) > 0)
					targetCount++;

				// set the move flag
				move = true;

				// historize a 'true' to indicate that the box was moved
				boxMoved.addElement(new Boolean(true));
			}
		}

		if (move) {
			// historize the position
			moves.addElement(new Integer(playerX + width * playerY));

			// move the player
			playerX = fromX;
			playerY = fromY;
		}

		return move;
	}

	/**
	 * Undo a move.
	 */
	public boolean undo() {
		int s = moves.size() - 1;
		if (s >= 0) {
			int pos = ((Integer) moves.elementAt(s)).intValue();
			int y = pos / width;
			int x = pos - y * width;
			if (((Boolean) boxMoved.elementAt(s)).booleanValue()) {
				int fromX = 2 * playerX - x;
				int fromY = 2 * playerY - y;
				working[fromX][fromY] ^= BOX;
				working[playerX][playerY] |= BOX;
				if ((working[fromX][fromY] & TARGET) > 0)
					targetCount--;
				if ((working[playerX][playerY] & TARGET) > 0)
					targetCount++;
			}
			moves.removeElementAt(s);
			boxMoved.removeElementAt(s);
			playerX = x;
			playerY = y;
		} else
			return false;
		return true;
	}

	public int getPlayerX() {
		return playerX;
	}

	public int getPlayerY() {
		return playerY;
	}

	public int getCell(int x, int y) {
		return working[x][y];
	}

	public int getWidth() {
		return width;
	}

	public int getHeight() {
		return height;
	}

	public int getMoveCount() {
		return moves.size();
	}

	public boolean isEnd() {
		return targetCount == boxCount;
	}

	public String getMoves() {
		int xs = playerXStart;
		int ys = playerYStart;
		int count = moves.size();
		if (count > 0) {
			byte result[] = new byte[count];
			moves.addElement(new Integer(playerX + width * playerY));
			for (int i = 1; i < count + 1; i++) {
				int p = ((Integer) moves.elementAt(i)).intValue();
				int yd = p / width;
				int xd = p - yd * width;
				byte b = 0;
				if (xd > xs) {
					b = 'r';
				} else if (xd < xs) {
					b = 'l';
				} else if (yd > ys) {
					b = 'd';
				} else if (yd < ys) {
					b = 'u';
				}
				result[i - 1] = b;
				xs = xd;
				ys = yd;
			}
			moves.removeElementAt(moves.size() - 1);
			return new String(result);
		} else {
			return "";
		}
	}
}