import java.awt.Dimension;
import java.awt.GridLayout;
import java.util.LinkedList;

import javax.swing.*;

public class AStern {


	//Definieren der Variablen
	public static LinkedList<Node> que = new LinkedList<Node>();
	public static LinkedList<Node> visited = new LinkedList<Node>();

	public static int[][] arr_feld = new int[10][10];

	public static int StartX = 1;
	public static int StartY = 1;

	public static int TargetX = arr_feld[0].length-1;
	public static int TargetY = arr_feld[1].length-1;


	public static int QueCounter = 0;
	public static int GlobalCounter = 0;
	public static void getNeighbor(int x, int y) {
		/*
		 * Abfragen der 4 Umliegenden felder
		 * 		Y-1
		 * 	X-1		X+1
		 *		Y+1
		 */
		System.out.println(x + " " + y);


		if (y-1 >=0) {
			addQue(x, y-1);
		}
		if (y+1 <arr_feld[1].length) {
			addQue(x, y+1);
		}

		if (x-1 >=0) {
			addQue(x-1, y);
		}

		if (x+1 <arr_feld[0].length) {
			addQue(x+1, y);
		}
	}

	public static void addQue(int x, int y) {
		//Erstellung des Objektes welches in que gespeichert wird
		Node n = new Node();
		n.setX(x);
		n.setY(y);
		n.setCost(calcCost(x,y));
		//Überprüfen ob Objekt schon gespeichert wurde
		QueCounter++;
		if (!que.contains(n) && !visited.contains(n)) {
			if (x-1 != TargetX && x-1 != TargetX && y != TargetY && y != TargetY) {
				//Objekt zu que hinzufügen
				que.add(n);
				//arr_feld[x][y] = 1;
				//Visuelle Darstellung welche zahl ausgewählt wurde
				if(QueCounter == 4) {
					QueCounter = 0;

					getMinCost();

				}
			} else {
				System.out.println("Ende" + x + "/" + y + "|" + TargetX + "/" + TargetY);
			}
		}
	}

	public static void getMinCost() {
		int min = -1;
		int index;
		int current;
		int x = 0;
		int y = 0;
		//für jedes object in que
		for (int i = 0; i < que.size(); i++) {
			Node n = que.get(i);

			//Zur initalisierung die erste zahl in  min speichern
			current = n.getCost();
			if (min == -1) {
				min = n.getCost();
				index = i;
				x= n.getX();
				y = n.getY();
			}

			//wenn die momentane Zahl kleiner als die gespeicherte ist, ersetzte sie.
			if (current < min) {
				index = i;
				min = n.getCost();
				x= n.getX();
				y = n.getY();
			}
		}
		output();

		//Objekt von que löschen und in visited speichern
		int counter = que.size()-1;
		for (int i = 0; i < counter; i++) {
			visited.add(que.get(i));
		}
		que.clear();


		//Visuelle Darstellung welche zahl ausgewählt wurde
		arr_feld[x][y] = 2;

		//Nachbar mit der Niedrigsten Zelle aufrufen
		getNeighbor(x, y);

	}

	public static void output() {
		for (int i = 0; i < arr_feld[0].length; i++) {
			for (int j = 0; j < arr_feld[1].length; j++) {
				System.out.print(arr_feld[i][j] + " \t");
			}
			System.out.println();
		}
		arr_feld[TargetX][TargetY] = 999;
		System.out.println("\n");
	}

	public static int calcCost(int x, int y) {
		/*
		 * Berechnen der kosten anhand der 'Manhatten Distance'
		 * |Xstart - Xziel)| + |(Ystart - Yziel)|
		 */

		int cost = (int) Math.abs((x - TargetX) + (y - TargetY));
		return cost;
	}

	public static void main(String[] args) {
		getNeighbor(StartX, StartY);

	}

}