vladmiriteam

 import static java.lang.System.out;

import java.util.*;

import agents.ArtificialAgent;
import game.actions.EDirection;
import game.actions.compact.*;
import game.board.compact.BoardCompact;
import game.board.compact.CTile;

/**
 * The simplest Tree-DFS agent.
 * @author Jimmy
 */
public class MyAgent extends ArtificialAgent {
	class MyState {
		public static final int Y_MASK = (Integer.MAX_VALUE >> 16);

		/**
		 * PLAYER
		 * [0] = player-x, player-y
		 *
		 * BOXES (for n>0)
		 * [n] = nth-box-x (the first 16bits), nth-box-y (the second 16bits)
		 */
		int player;
		long positions;

		/**
		 * Extract minimal state from 'board'
		 * @param board
		 */

		/**
		 * Extract minimal state from 'board'
		 * @param board
		 */
		public MyState(BoardCompact board) {
			player = getPacked(board.playerX, board.playerY);
			positions = 0;
			for (int x = 0; x < board.width(); ++x) {
				for (int y = 0; y < board.height(); ++y) {
					if (CTile.isSomeBox(board.tile(x, y))) {
						positions |= (1L << toBit(x, y));
					}
				}
			}
		}

		public MyState(MyState state) {
			this.player = state.player;
			this.positions = state.positions;
		}

		public boolean containsBox(long val) {
			return (positions & val) != 0;
		}

		public void reverseMove(int dirVal) {
			EDirection dir = EDirection.arrows()[(dirVal >> 1)];
			int currCellX = getX(player);
			int currCellY = getY(player);
			long currBit = (1L << toBit(currCellX, currCellY));
			int prevPacked = getPacked(currCellX - dir.dX, currCellY - dir.dY);
			updatePlayer(prevPacked);

			if ((dirVal & 1) == 1) {
				long nextBit = (1L << toBit(currCellX + dir.dX, currCellY + dir.dY));
				updateBit(nextBit, currBit);
			}
		}

		public void updatePlayer(int newVal) {
			player = newVal;
		}

		public void updateBit(long oldBit, long newBit) {
			positions ^= oldBit;
			positions |= newBit;
		}

		/**
		 * Packs [x;y] into single integer.
		 * @param x
		 * @param y
		 * @return
		 */
		public int getPacked(int x, int y) {
			return x << 16 | y;
		}

		/**
		 * Returns X coordinate from packed value.
		 * @param packed
		 * @return
		 */
		public int getX(int packed) {
			return packed >> 16;
		}

		/**
		 * Returns Y coordinate from packed value.
		 * @param packed
		 * @return
		 */
		public int getY(int packed) {
			return packed & Y_MASK;
		}

		public int hashCode() {
			return (int)(positions % (1e9 + 7)) + (player << 16);
		}

		public int toBit(int x, int y) {
			return bitVal[x][y];
		}

		@Override
		public boolean equals(Object o) {
			if (this == o) return true;
			if (o == null || getClass() != o.getClass()) return false;
			MyState myState = (MyState) o;
			return player == myState.player && positions == myState.positions;
		}

		@Override
		public String toString() {
			int pX = getX(player);
			int pY = getY(player);
			String s = pX + " " + pY + "\n";
			for (int i = 0; i < 64; ++i) {
				if ((positions & (1L << i)) != 0) {
					int x = getXbit(i);
					int y = getYbit(i);
					s += Integer.toString(x) + " " + Integer.toString(y) + "\n";
				}
			}
			s += "-------------\n";
			return s;
		}

		int getXbit(int bit) {
			return xValue[bit];
		}

		int getYbit(int bit) {
			return yValue[bit];
		}
	}


	static class Node implements Comparable<Node> {
		public Node(MyState state, int action, int g, int h) {
			this.state = state;
			this.action = action;
			this.g = g;
			this.h = h;
		}

		MyState state;
		int action;

		int g, h;

		@Override
		public int compareTo(Node other) {
			if (g + h == other.g + other.h) {
				return Integer.compare(h, other.h);
			}
			return Integer.compare(g + h, other.g + other.h);
		}
	}

	static protected BoardCompact board;
	static long endGoal;
	protected int searchedNodes;
	private static int[] boxesX;
	private static int[] boxesY;

	static boolean[][] dead;

	static int[][] bfsDist;
	private static int[] xValue;
	private static int[] yValue;
	private static int[][] bitVal;


	private void computeBfs() {
		Queue<int[]> q = new LinkedList<>();
		for (int x = 0; x < board.width(); ++x)
			for (int y = 0; y < board.height(); ++y) {
				if (CTile.forSomeBox(board.tile(x, y))) {
					bfsDist[x][y] = 0;
					q.offer(new int[]{x, y});
				} else {
					bfsDist[x][y] = -1;
				}
			}
		while (!q.isEmpty()) {
			int[] cell = q.poll();
			for (EDirection dir: EDirection.arrows()) {
				int neighX = cell[0] + dir.dX;
				int neighY = cell[1] + dir.dY;
				if (!CTile.isWall(board.tile(cell[0], cell[1])) && bfsDist[neighX][neighY] == -1) {
					bfsDist[neighX][neighY] = 1 + bfsDist[cell[0]][cell[1]];
					q.offer(new int[]{neighX, neighY});
				}
			}
		}
	}

	private int computeBfsHeuristic() {
		int minCost = 0;
		for (int i = 0; i < boxesX.length; ++i) {
			if (bfsDist[boxesX[i]][boxesY[i]] == -1)
				return -1;
			minCost += bfsDist[boxesX[i]][boxesY[i]];
		}
		return minCost;
	}

	private int computeHeuristic() {
		int boxes = 0;
		endGoal = 0;
		for (int i = 0; i < board.height(); ++i)
			for (int j = 0; j < board.width(); ++j) {
				if (CTile.forSomeBox(board.tiles[j][i])) {
					endGoal |= (1L << bitVal[j][i]);
				}
				if (CTile.isSomeBox(board.tiles[j][i])) {

					if (dead[j][i]) return -1;

					boxesX[boxes] = j;
					boxesY[boxes] = i;
					++boxes;
				}
			}
		return computeBfsHeuristic();
	}

	@Override
	protected List<EDirection> think(BoardCompact board) {
		MyAgent.board = board.clone();
		bfsDist = new int[board.width()][board.height()];
		bitVal = new int[board.width()][board.height()];
		xValue = new int[board.width() * board.height()];
		yValue = new int[board.width() * board.height()];
		for (int x = 1; x < board.width() - 1; ++x)
			for (int y = 1; y < board.height() - 1; ++y) {
				int val = (y - 1) * (board.width() - 2) + (x - 1);
				bitVal[x][y] = val;
				xValue[val] = x;
				yValue[val] = y;
			}
		computeBfs();
		boxesX = new int[board.boxCount];
		boxesY = new int[board.boxCount];
		searchedNodes = 0;
		long searchStartMillis = System.currentTimeMillis();

		List<EDirection> result = AStar();

		long searchTime = System.currentTimeMillis() - searchStartMillis;

        if (verbose) {
            out.println("Nodes visited: " + searchedNodes);
            out.printf("Performance: %.1f nodes/sec\n",
                        ((double)searchedNodes / (double)searchTime * 1000));
        }

		return result.isEmpty() ? null : result;
	}

	static boolean isVictory(MyState state) {
		return state.positions == endGoal;
	}

	private List<EDirection> AStar() {
		dead = DeadSquareDetector.detect(board);
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(new MyState(board), -1, 0, computeHeuristic()));
		HashMap<MyState, Integer> from = new HashMap<>();
		MyState goal = null;
		int k = 0;
		while (!pq.isEmpty()) {
			Node node = pq.poll();
			searchedNodes++;
			if (from.containsKey(node.state))
				continue;

			from.put(node.state, node.action);

			if (isVictory(node.state)) {
				goal = node.state;
				k = node.g;
				break;
			}

			int playerX = node.state.getX(node.state.player);
			int playerY = node.state.getY(node.state.player);

			for (EDirection dir: EDirection.arrows()) {
				int neighX = playerX + dir.dX;
				int neighY = playerY + dir.dY;
				if (CTile.isWall(board.tiles[neighX][neighY]))
					continue;
				int movedBox = node.state.getPacked(neighX, neighY);
				int oldBit = node.state.toBit(neighX, neighY);
				long boxBit = (1L << oldBit);
				if (node.state.containsBox(boxBit)) {
					int newBoxPosX = neighX + dir.dX;
					int newBoxPosY = neighY + dir.dY;
					int newBit = node.state.toBit(newBoxPosX, newBoxPosY);
					long freeSpaceBit = (1L << newBit);
					if (!CTile.isWall(board.tiles[newBoxPosX][newBoxPosY]) && !node.state.containsBox(freeSpaceBit)) {
						if (bfsDist[newBoxPosX][newBoxPosY] == -1 || dead[newBoxPosX][newBoxPosY])
							continue;
						MyState newState = new MyState(node.state);
						newState.updatePlayer(movedBox);
						newState.updateBit((1L << oldBit), (1L << newBit));
						if (!from.containsKey(newState)) {
							int heuristic = node.h - bfsDist[neighX][neighY] + bfsDist[newBoxPosX][newBoxPosY];
							pq.add(new Node(newState, (dir.index << 1) | 1, node.g + 1, heuristic));
						}
					}
				} else {
					MyState newState = new MyState(node.state);
					newState.updatePlayer(movedBox);
					if (!from.containsKey(newState)) {
						pq.add(new Node(newState, (dir.index << 1), node.g + 1, node.h));
					}
				}
			}
		}

		List<EDirection> result = new ArrayList<>();
		while (k > 0) {
			int dir = from.get(goal);
			goal = new MyState(goal);
			result.add(EDirection.arrows()[dir >> 1]);
			goal.reverseMove(dir);
			k--;
		}
		Collections.reverse(result);
		return result;
	}
}

class DeadSquareDetector {

	 static boolean[][] detect(BoardCompact board) {
		boolean[][] dead = new boolean[board.width()][board.height()];
		Queue<int[]> Q = new LinkedList<>();
		for (int x = 0; x < board.width(); ++x)
			for (int y = 0; y < board.height(); ++y)
				if (CTile.forSomeBox(board.tile(x, y))) {
					Q.offer(new int[]{x, y});
					dead[x][y] = false;
				} else {
					dead[x][y] = true;
				}
		while (!Q.isEmpty()) {

			int[] cell = Q.poll();
			for (EDirection dir: EDirection.arrows()) {
				int neighX = cell[0]+ dir.dX;
				int neighY = cell[1] + dir.dY;
				if (!CTile.isWall(board.tile(neighX, neighY)) && dead[neighX][neighY]) {
					int newNeighX = neighX + dir.dX;
					int newNeighY = neighY + dir.dY;
					if (!CTile.isWall(board.tile(newNeighX, newNeighY))) {
						Q.offer(new int[]{neighX, neighY});
						dead[neighX][neighY] = false;
					}
				}
			}

		}
		return dead;
	}
}