AuK/Näherungsverfahren 1 SS10

Wiki-Quelltext dieser Seite.

<code>
import java.io.*;
import java.util.*;

public class WarnsdorfalgorithmusArray {
	private static final String FileInputName = "springerin.txt";
	private static final String FileOutputName = "springerout.txt";
	private static final int nx[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
	private static final int ny[] = { -1, 1, -2, 2, -2, 2, -1, 1 };

	private static boolean imSchachbrett(int x, int y, int m, int n) {
		return ((0 <= x && x < m) && (0 <= y && y < n));
	}

	private static int möglicheSchritte(int a[][], int m, int n, int x, int y) {
		int anzahl = 0;
		int xn, yn;
		for (int i = 0; i < 8; i++) {
			xn = x + nx[i];
			yn = y + ny[i];
			if (imSchachbrett(xn, yn, m, n) && a[xn][yn] == 0)
				anzahl++;
		}
		return anzahl;
	}

	static boolean findeBestenWeg(int a[][], int m, int n, int xy[]) {
		int aux = Integer.MAX_VALUE;
		int xn, yn, xx = 0, yy = 0;
		for (int i = 0; i < 8; i++) {
			xn = xy[0] + nx[i];
			yn = xy[1] + ny[i];
			if (imSchachbrett(xn, yn, m, n) && a[xn][yn] == 0) {
				int schritte = möglicheSchritte(a, m, n, xn, yn);
				if (schritte < aux) {
					aux = schritte;
					xx = xn;
					yy = yn;
				}
			}
		}
		if (aux < Integer.MAX_VALUE) {
			xy[0] = xx;
			xy[1] = yy;
			return true;
		}
		return false;
	}

	public static void main(String[] args) {
		Scanner scanner = null;
		//PrintStream out = null;
		BufferedReader eingabe = new BufferedReader( new InputStreamReader(System.in));
		String temp="";
		try {
			scanner = new Scanner(new File(FileInputName));
			//out = new PrintStream(new File(FileOutputName));
			//eingabe(args);
			int m = 0; //scanner.nextInt();
			int n = 0; //scanner.nextInt();
			int l = 0; //scanner.nextInt();
			int c = 0; //scanner.nextInt();
			System.out.println("Geben Sie 'n' eines n*m Schachbretts an : ");
			try {
				temp = eingabe.readLine();
				n = Integer.parseInt(temp);
			}
			catch(IOException e){
				System.out.println("Fehler");
			}
			
			System.out.println("Geben Sie 'm' eines n*m Schachbretts an : ");
			try {
				temp = eingabe.readLine();
				m = Integer.parseInt(temp);
			}
			catch(IOException e){
				System.out.println("Fehler");
			}
			
			System.out.println("Geben Sie die x-Koordinate des Springers an: ");
			try {
				temp = eingabe.readLine();
				l = Integer.parseInt(temp);
			}
			catch(IOException e){
				System.out.println("Fehler");
			}
			
			System.out.println("Geben Sie die y-Koordinate des Springers an: ");
			try {
				temp = eingabe.readLine();
				c = Integer.parseInt(temp);
			}
			catch(IOException e){
				System.out.println("Fehler");
			}
			l--;
			c--;
			int[][] a = new int[m][n];
			a[l][c] = 1;
			int ctr = 1;
			int xy[] = new int[2];
			xy[0] = 1;
			xy[1] = c;
			while (findeBestenWeg(a, m, n, xy)) {
				a[xy[0]][xy[1]] = ++ctr;
			}
			/*if (ctr == m * n) {
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						out.printf("%4d", a[i][j]);
					}
					out.println();
				}
			} else {
				out.println("Keine Lösung!");

			}
*/
			if (ctr == m * n) {
				for (int i = 0; i < n; i++) {
					System.out.println();
					System.out.println();
					for (int j = 0; j < n; j++) {
						System.out.print("\t"+a[i][j] + "\t");
					}
				}
			}else System.out.println("keine Lösung !!");
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} finally {
			if (scanner != null) {
				scanner.close();

				// if (out != null) {
				// out.close();
			}
		}
	}

}
</code>
<eval></eval>