Create a new version of paste:

import java.io.*;
import java.util.*;

class FI12HW02
	
	{
	
	private static HashSet<SearchNode> nodes; // Configuration nodes set
	
	// Main method
	
	public static void main(String[] args) throws Exception
		{
		System.out.println(solve());
		}
	
	// Solving method (main), builds the structure and calls auxiliary method. Time: Unknown
	
	public static int solve() throws IOException
		{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		StringTokenizer st = new StringTokenizer(line);
		String nextToken = st.nextToken();
		int[][] puzzle = new int[4][4];
		for(int i = 0; i < 4; i++) // Building the initial matrix
			{
			for(int j = 0; j < 4; j++)
				{
				puzzle[i][j] = Integer.parseInt(nextToken);
				if(st.hasMoreTokens()) nextToken = st.nextToken();
				}
			line = br.readLine();
			if(line != null) st = new StringTokenizer(line);
			if(st.hasMoreTokens()) nextToken = st.nextToken();
			}
		SearchNode first = new SearchNode(puzzle, 0, null); // Initializes first node in sequence to initial configuration
		nodes = new HashSet<SearchNode>(20, 0.5f);
		return minDistance(first); // Calculates the minimum number of moves necessary
		}
	
	// Calculates minimum moves. Time: Unknown
	
	private static int minDistance(SearchNode n)
		{
		if(n.isFinal()) return n.moves;
		int[][] up = moveUp(n.config);
		int[][] down = moveDown(n.config);
		int[][] left = moveLeft(n.config);
		int[][] right = moveRight(n.config);
		if((n.previous == null || !n.previous.notMoved(up)) && !n.notMoved(up)) nodes.add(new SearchNode(up, n.moves + 1, n));
		if((n.previous == null || !n.previous.notMoved(down)) && !n.notMoved(down)) nodes.add(new SearchNode(down, n.moves + 1, n));
		if((n.previous == null || !n.previous.notMoved(left)) && !n.notMoved(left)) nodes.add(new SearchNode(left, n.moves + 1, n));
		if((n.previous == null || !n.previous.notMoved(right)) && !n.notMoved(right)) nodes.add(new SearchNode(right, n.moves + 1, n));
		SearchNode next = removeMin();
		return minDistance(next);
		}
	
	// Takes an input configuration and returns the node containing the following configuration, moving up the first free square. Time: O(n^2)
	
	private static int[][] moveUp(int[][] m)
		{
		int[][] out = new int[4][4];
		boolean substituted = false;
		int switchedRow = -1;
		int switchedColumn = -1;
		for(int i = 0; i < 4; i++)
			{
			for(int j = 0; j < 4; j++)
				{
				if(m[i][j] == 0 && !substituted && i < 3)
					{
					out[i][j] = m[i + 1][j];
					out[i + 1][j] = 0;
					substituted = true;
					switchedRow = i + 1;
					switchedColumn = j;
					}
				else
					{
					if(i != switchedRow || j != switchedColumn)
						out[i][j] = m[i][j];
					}
				}
			}
		return out;
		}
	
	// Takes an input configuration and returns the node containing the following configuration, moving down the first free square. Time: O(n^2)
	
	private static int[][] moveDown(int[][] m)
		{
		int[][] out = new int[4][4];
		boolean substituted = false;
		int switchedRow = -1;
		int switchedColumn = -1;
		for(int i = 0; i < 4; i++)
			{
			for(int j = 0; j < 4; j++)
				{
				if(m[i][j] == 0 && !substituted && i > 0)
					{
					out[i][j] = m[i - 1][j];
					out[i - 1][j] = 0;
					substituted = true;
					switchedRow = i - 1;
					switchedColumn = j;
					}
				else
					{
					if(i != switchedRow || j != switchedColumn)
						out[i][j] = m[i][j];
					}
				}
			}
		return out;
		}
	
	// Takes an input configuration and returns the node containing the following configuration, moving left the first free square. Time: O(n^2)
	
	private static int[][] moveLeft(int[][] m)
		{
		int[][] out = new int[4][4];
		boolean substituted = false;
		int switchedRow = -1;
		int switchedColumn = -1;
		for(int i = 0; i < 4; i++)
			{
			for(int j = 0; j < 4; j++)
				{
				if(m[i][j] == 0 && !substituted && j < 3)
					{
					out[i][j] = m[i][j + 1];
					out[i][j + 1] = 0;
					substituted = true;
					switchedRow = i;
					switchedColumn = j + 1;
					}
				else
					{
					if(i != switchedRow || j != switchedColumn)
						out[i][j] = m[i][j];
					}
				}
			}
		return out;
		}
	
	// Takes an input configuration and returns the node containing the following configuration, moving right the first free square. Time: O(n^2)
	
	private static int[][] moveRight(int[][] m)
		{
		int[][] out = new int[4][4];
		boolean substituted = false;
		int switchedRow = -1;
		int switchedColumn = -1;
		for(int i = 0; i < 4; i++)
			{
			for(int j = 0; j < 4; j++)
				{
				if(m[i][j] == 0 && !substituted && j > 0)
					{
					out[i][j] = m[i][j - 1];
					out[i][j - 1] = 0;
					substituted = true;
					switchedRow = i;
					switchedColumn = j - 1;
					}
				else
					{
					if(i != switchedRow || j != switchedColumn)
						out[i][j] = m[i][j];
					}
				}
			}
		return out;
		}
	
	// Removes and returns the minimum distance node in the list. Time: O(n)
	
	private static SearchNode removeMin()
		{
		SearchNode out = null;
		int manhMin = Integer.MAX_VALUE;
		Iterator<SearchNode> it = nodes.iterator();
		while(it.hasNext())
			{
			SearchNode n = (SearchNode)it.next();
			if(n.manhattan + n.moves < manhMin)
				{
				out = n;
				manhMin = n.manhattan + n.moves;
				}
			}
		nodes.remove(out);
		return out;
		}
	
	// SearchNode class
	
	static class SearchNode
		{
		
		int[][] config;
		int moves;
		SearchNode previous;
		int manhattan;
		
		SearchNode(int[][] config, int moves, SearchNode previous)
			{
			this.config = config;
			this.moves = moves;
			this.previous = previous;
			manhattan = manhattanDistance();
			}
		
		// Checks if the given configuration is final. Time: O(1)
		
		boolean isFinal()
			{
			return (config[0][0] == 1 && config[0][1] == 2 && config[0][2] == 3 && config[0][3] == 4 &&
					config[1][0] == 5 && config[1][1] == 6 && config[1][2] == 7 && config[1][3] == 8 &&
					config[2][0] == 9 && config[2][1] == 10 && config[2][2] == 11 && config[2][3] == 12 &&
					config[3][0] == 13 && config[3][1] == 14 && config[3][2] == 15 && config[3][3] == 0);
			}
		
		// Checks if the given node has the same configuration as the current node. Time: O(1)
		
		boolean notMoved(int[][] m)
			{
			return (config[0][0] == m[0][0] && config[0][1] == m[0][1] && config[0][2] == m[0][2] && config[0][3] == m[0][3] &&
					config[1][0] == m[1][0] && config[1][1] == m[1][1] && config[1][2] == m[1][2] && config[1][3] == m[1][3] &&
					config[2][0] == m[2][0] && config[2][1] == m[2][1] && config[2][2] == m[2][2] && config[2][3] == m[2][3] &&
					config[3][0] == m[3][0] && config[3][1] == m[3][1] && config[3][2] == m[3][2] && config[3][3] == m[3][3]);
			}
		
		// Calculates the current node's Manhattan distance. Time: O(n^2)
		
		int manhattanDistance()
			{
			int manh = 0;
			for(int i = 0; i < 4; i++)
				{
				for(int j = 0; j < 4; j++)
					{
					if(config[i][j] == 1)
						manh = manh + Math.abs(i) + Math.abs(j);
					else if(config[i][j] == 2)
						manh = manh + Math.abs(i) + Math.abs(j - 1);
					else if(config[i][j] == 3)
						manh = manh + Math.abs(i) + Math.abs(j - 2);
					else if(config[i][j] == 4)
						manh = manh + Math.abs(i) + Math.abs(j - 3);
					else if(config[i][j] == 5)
						manh = manh + Math.abs(i - 1) + Math.abs(j);
					else if(config[i][j] == 6)
						manh = manh + Math.abs(i - 1) + Math.abs(j - 1);
					else if(config[i][j] == 7)
						manh = manh + Math.abs(i - 1) + Math.abs(j - 2);
					else if(config[i][j] == 8)
						manh = manh + Math.abs(i - 1) + Math.abs(j - 3);
					else if(config[i][j] == 9)
						manh = manh + Math.abs(i - 2) + Math.abs(j);
					else if(config[i][j] == 10)
						manh = manh + Math.abs(i - 2) + Math.abs(j - 1);
					else if(config[i][j] == 11)
						manh = manh + Math.abs(i - 2) + Math.abs(j - 2);
					else if(config[i][j] == 12)
						manh = manh + Math.abs(i - 2) + Math.abs(j - 3);
					else if(config[i][j] == 13)
						manh = manh + Math.abs(i - 3) + Math.abs(j);
					else if(config[i][j] == 14)
						manh = manh + Math.abs(i - 3) + Math.abs(j - 1);
					else if(config[i][j] == 15)
						manh = manh + Math.abs(i - 3) + Math.abs(j - 2);
					else;
					}
				}
			return manh;
			}
		
		}
	
	}