/* Programm von Michael Mardaus und Tobias Nagel
 * Einführung in die Programmierung
 * Übungsgruppe 5 Rene Pickhardt
 * Blatt 10 Aufgabe 1
 * Ein Springerproblem
 */
package mardaus.blatt11;
import java.util.Scanner;

class aufgabe2{
	
//Funktion zum Einlesen einer Benutzereingabe 
//Rückgabe: Integer
	public static int getInput(){
		Scanner s = new Scanner(System.in);
		return s.nextInt();
	}//End getInput

/*doMatrix Initialisiert Grundgerüst für Adjazenzmatrix, d.h.
* Einheitsmatrix der Dimension n²xn²
* Rückgabe: 2dim Integer Feld 
* Input: Schachbrettgröße n (integer) */
	public static int [][] doMatrix(int n){
		int [][] Matrix=new int[n*n][n*n];
		for(int i=0;i<n*n;i++)
			for(int j=0;j<n*n;j++){
				Matrix[i][j]=0;
				// if(i==j) Matrix[i][i]=1;
			}
		return Matrix;
	}//End doMatrix
	
/* fillMatrix berechnet die Adjazenzmatrix eines Springers nach Schachregeln
 * Denke die Felder des Schachbretts durchnummeriert von 0 bis n²-1
 * Rückgabe: void
 * Input: 2dim Feld (integer) */
	public static void fillMatrix(int [][]Matrix){
		int n = (int) Math.sqrt(Matrix.length);
		for(int i=0;i<n; i++){//Zeilenindex i
			for(int j=0; j<n; j++){//Spaltenindex j
				if(i-2>=0){    							    //zwei Felder nach oben
					if(j-1>=0) Matrix[i*n+j][(i-2)*n+j-1]=1;//ein Feld nach links
					if(j+1< n) Matrix[i*n+j][(i-2)*n+j+1]=1;//ein Feld nach rechts
				}
				if(i-1>=0){                                 //ein Feld nach oben
					if(j-2>=0) Matrix[i*n+j][(i-1)*n+j-2]=1;//zwei Felder nach links
					if(j+2< n) Matrix[i*n+j][(i-1)*n+j+2]=1;//zwei Felder nach rechts
				}
				if(i+1<n){									//ein Feld nach unten
					if(j-2>=0) Matrix[i*n+j][(i+1)*n+j-2]=1;//zwei Felder nach links
					if(j+2< n) Matrix[i*n+j][(i+1)*n+j+2]=1;//zwei Felder nach rechts
				}
				if(i+2<n){									//zwei Felder nach unten
					if(j-1>=0) Matrix[i*n+j][(i+2)*n+j-1]=1;//ein Feld nach links
					if(j+1< n) Matrix[i*n+j][(i+2)*n+j+1]=1;//ein Feld nach rechts
				}	
			}
		}
	}//End fillMatrix
	
/*ausgabeMatrix erzeugt Aufgabe der übergebenen Matrix auf der
 * Konsole [Input: 2dim Feld (integer)] */
	public static void ausgabeMatrix(int[][]Matrix){
		int n=Matrix.length;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)
				System.out.print(Matrix[i][j]);
		System.out.println();
		}
	}//End ausgabeMatrix
	
	/* funktion die den kuerzesten weg per breitensuche bestimmt
	 * input: die adj.matrix, das startfeld und das endfeld
	 * output: die laenge des weges
	 * keine kommentare, weil identisch zu eins (bis auf nullmengen)
	 */
	public static int anzahlZuege(int[][]Matrix, int start, int ziel){
		try{
		int n=Matrix.length;
		int head, tail;
		boolean flagge;
		int [] queue=new int[n];
		int [] vorgaenger = new int[n];
		fertig = false;
		zahl=1;
		
		head = tail = 0;
		queue[0]=start;
		vorgaenger[0]=-1;  
		
		while (head <= tail) {
			int x = queue[head];
			head++;
			
			for(int i=0;i<n;i++){
				flagge=false;
				if(Matrix[x][i]==1){
					if(i==ziel) {
						vorgaenger[tail+1]=x;
						queue[tail+1]=ziel;
						return auswerten(queue,vorgaenger,start,ziel); 
					}
					for(int j=0; j<=tail; j++)
						if(queue[j]==i) flagge=true;
					if(!flagge){
						tail++;
						queue[tail]=i;
						vorgaenger[tail]=x;
					}
				}
			}
		}
		return -1; // fehlercode fuer kein weg gefunden
		}
		catch (ArrayIndexOutOfBoundsException e){
			return -2; // eingabefehler
		}
			
	}//end anzahlZuege
	
	static int zahl = 1;
	static boolean fertig = false;
	
	/* funktion zum auswerten der wege
	 * input: die queue, das vorgaengerfeld, start und ziel des weges
	 * output: die laenge des weges zwischen start und ziel
	 * keine kommentare weil identisch in 1
	 */
	public static int auswerten(int[]queue, int []vorgaenger, int start, int ziel){
		if (start==ziel) return 0;
		
		int vorg = vorgaenger[indexOf(ziel,queue)];
		if (start==vorg) fertig = true;
		while(start!=vorg && !fertig){
			zahl++;
			auswerten(queue,vorgaenger,start,vorg);
		}
		return zahl;
	}
	
	/* input: das zusuchende element als erster parameter und das
	 * zu durchsuchende feld im zweiten
	 * output: der index des elements in der menge
	 */
	public static int indexOf(int zahl,int[] feld){
		for(int i=0;i<feld.length;i++)
			if(feld[i]==zahl) return i;
		return -1;
	}
	
	public static void main (String argv[]){
		int board_size;
		int [][] Adjazenzmatrix;
		
		System.out.print("Wie groß soll das Schachbrett sein? n= ");
		board_size = getInput();
		Adjazenzmatrix = doMatrix(board_size);
		fillMatrix(Adjazenzmatrix);
		//System.out.println("Sie Adjazenzmatrix lautet:");
		//ausgabeMatrix(Adjazenzmatrix);
		System.out.println("Die Felder sind von 0 bis "+(board_size*board_size-1)+" nummeriert");
		System.out.print("Ihr Startfeld bitte: ");
		int erstesfeld=getInput();
		System.out.print("Und nun bitte Ihr Zielfeld: ");
		int zweitesfeld=getInput();
		
		int erg = anzahlZuege(Adjazenzmatrix, erstesfeld, zweitesfeld);
		if (erg < 0) { // eingabe fehler
			System.out.println("UserOutOfIntelligenceException at Eingabe");
			return;
		}
		System.out.println("Das geht in "+erg+" Zuegen.");
		
		// hier alle moeglichen zuege probieren um max zu finden
		System.out.print("Bei diesem Schachbrett ");
		int max = 0;
		for(int i=0;i<board_size*board_size;i++)
			for(int j=0;j<board_size*board_size;j++){
				int hugo = anzahlZuege(Adjazenzmatrix, i, j);
				if (max<hugo) max = hugo;
			}
		System.out.println("erreicht man jedes Feld mit maximal "+max+" Sprüngen!");
				
		
	}//End main
	
}//End class