Problém nájdenia cesty v bludisku

Created: 2008-06-19 - 16:46

Podivny algoritmus na prehladavanie ci existuje cesta v bludisku (s vypisovanim postupov - zatial. pribudne aj vypisanie len spravnej cesty) takym sposobom, ze si oznacuje kazde razcestie a ked sa dostane do slepej ulicky tak sa vrati naspat... odskusane na tomto bludisku: 


############################
#S.....##...################
##.#.#.##.#.######..K#######
##.#.#.#########...#########
######.#########.###....####
#.##...##...####.#.#.##...##
#....#.##.#.####.#.#.##.#..#
#.##.####.#......#.#....####
#.##...##.######.#.#.##.#.##
#.##.#.##.######.#...##....#
#.##.#.##........#.#########
#.####.#########.........###
#.##......#####..#######.###
#.##.#.##.######.#.........#
#.##.####........#.###..####
#....#############.....#####
############################




import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Bludisko {
	public static void main(String[] args) {
		// Zadanie cesty pre bludisko - nacitanie zo suboru:
		File mapaBludiska;
		Scanner sc = new Scanner("null");
		try {
			mapaBludiska = new File("H:\\mapaBludiska");
			/*
			 * mapaBludiska je subor obsahujuci mapu bludiska, kde #
			 * reprezentuju steny, . reprezentuju volnu cestu a S je start a K
			 * je koniec.
			 */
			sc = new Scanner(mapaBludiska);
		} catch (FileNotFoundException e) {
			System.out.print("Cisty koniec, bo toten subor nebol najdeny.");
		}
		char mapa[][] = new char[50][50];
		String riadok;
		int j = 0;
		int i = 0;
		int startx = 0;
		int starty = 0;
		while (sc.hasNextLine()) {
			riadok = sc.nextLine();
			for (i = 0; i < riadok.length(); i++) {
				mapa[i][j] = riadok.charAt(i);
				if (mapa[i][j] == 'S') {
					startx = i;
					starty = j;
				}
				System.out.print(mapa[i][j]);
			}
			System.out.println();
			j++;
		}
		// Hladanie cesty:
		boolean cestaNajdena = false;
		int x = startx;
		int y = starty;
		int pocitadlo = 0;
		int ktoreRazcestie = -1;
		int[] razcestiex = new int[100];
		int[] razcestiey = new int[100];
		boolean navstivene[][] = new boolean[50][50];
		String[] vyslednaCesta = new String[100];
		int cislo = -1;
		int pom=0;
		do {
			cislo++;
			if (zistiPocetSmerov(mapa, x, y, navstivene) > 1) {
				pom = cislo;
				System.out.println(zistiPocetSmerov(mapa, x, y, navstivene)+" smery");
				ktoreRazcestie++;
				razcestiex[ktoreRazcestie] = x;
				razcestiey[ktoreRazcestie] = y;
			}
			if (mapa[x + 1][y] == '.' && !navstivene[x + 1][y]) {
				x = x + 1;
				navstivene[x][y] = true;
				vyslednaCesta[cislo]=x+","+y;
			}
			else if (mapa[x][y - 1] == '.' && !navstivene[x][y - 1]) {
				y = y - 1;
				navstivene[x][y] = true;
				vyslednaCesta[cislo]=x+","+y;
			}
			else if (mapa[x - 1][y] == '.' && !navstivene[x - 1][y]) {
				x = x - 1;
				navstivene[x][y] = true;
				vyslednaCesta[cislo]=x+","+y;
			}
			else if (mapa[x][y + 1] == '.' && !navstivene[x][y + 1]) {
				y = y + 1;
				navstivene[x][y] = true;
				vyslednaCesta[cislo]=x+","+y;
			} else {
				x = razcestiex[ktoreRazcestie];
				y = razcestiey[ktoreRazcestie];
				System.out.println("Vraciam sa na "+ktoreRazcestie+". razcestie:"+x+","+y);
				ktoreRazcestie--;
				cislo=pom;
			}

			if (mapa[x + 1][y] == 'K' || mapa[x - 1][y] == 'K'
					|| mapa[x][y + 1] == 'K' || mapa[x][y - 1] == 'K')
				cestaNajdena = true;
			pocitadlo++;
			if (i * j * 2 < pocitadlo) {
				break;
			}
			System.out.print(x + "," + y + "|");

		} while (!cestaNajdena);
		
		System.out.println("Cesta najdena:" + cestaNajdena);
		for (int m = 0; m < j; m++) {
			for (int n = 0; n < i; n++) {
				System.out.print(mapa[n][m]);
			}
			System.out.println();
		}
		
		System.out.println("Ak chces vyjst zbludiska chod po suradniciach:");
		for(int u=0;u<50;u++){
			System.out.print("("+vyslednaCesta[u]+"),");
		}
	}

	public static int zistiPocetSmerov(char[][] mapa, int x, int y, boolean[][] navstivene) {
		int pocet = 0;
		if (mapa[x][y + 1] == '.' && !navstivene[x][y + 1])
			pocet++;
		if (mapa[x + 1][y] == '.' && !navstivene[x + 1][y])
			pocet++;
		if (mapa[x - 1][y] == '.' && !navstivene[x - 1][y])
			pocet++;
		if (mapa[x][y - 1] == '.' && !navstivene[x][y - 1])
			pocet++;
		return pocet;
	}
}