Witam
Mam za zadanie napisać program który znajdzie najkrótszą drogę w labiryncie.
Skorzystałem z prostego algorytmu http://www.algorytm.org/inne/najkrotsza-droga-w-labiryncie.html
Jedna coś do końca nie działa :/ - po dodaniu kontrolnych System.outów udało mi się wywnioskować, że do kolejki dziwnie się zachowuje - nie dodawane są te elementy które powinny.
Ciężko to trochę wytłumaczyć.
Tu jest wynik pierwszej pętli:
Punkt S znajduje się 6 8 - punkt startowy
Punkt F znajduje się 18 18 - meta
Punkt DO przerobienia 6 8 - zaczynamy od punktu startowego - sprawdzamy wszystkie 4 kierunki
Punkty tymczas 1 6 7 - tu możemy iść - if wyświetla mi ten punkt i dodaje go do kolejki
Punkty tymczas 3 6 9 - tu możemy iść - if wyświetla mi ten punkt i dodaje go do kolejki
długość kolejki 2 - sprawdzam jak duża jest kolejka - jest OK
Punkt przerobiony 6 8 - sprawdzam czy wszystko ok z przerobionym punktem - desperacja..
Punkt z kolejki 6 9 - wczytuje punkt z kolejki za pomocą poll - i tu zonk bo powinien być 6 7 bo dodałem go jako pierwszego
długość kolejki 22222222 1 - sprawdzam dl kolejki - OK
następny element 6 9 - zonk nr 2 - drugim elementem jest także 6 9
Kod wyrzuca NullPointera bo na koniec odwołuje się do pustego pola wziętego z kolejki, ale to nie ważne jest w tym momencie bo gdyby kolejka dobrze działała to zanim się opróżni to znajdzie metę.
Tu jest .gz który zawiera labirynt
https://drive.google.com/file/d/0BzDmQvXXd-TBOWJVN2JEZUNPSVU/edit?usp=sharing
import java.io.*;
import java.util.*;
import java.util.zip.GZIPInputStream;
import java.util.zip.GZIPOutputStream;
import javax.swing.JFileChooser;
import java.util.LinkedList;
import java.util.logging.Level;
import java.util.logging.Logger;
class Labirynt {
public static char[][] labirynt;
public class Punkt{
int wspX;
int wspY;
}
public Labirynt()
{
JFileChooser plik = new JFileChooser();
int status = plik.showOpenDialog(null);
if (status == JFileChooser.APPROVE_OPTION)
{
File nazwaPliku = plik.getSelectedFile();
int status2 = plik.showSaveDialog(null);
if (status2 == JFileChooser.APPROVE_OPTION)
{
File nazwaCelu = plik.getSelectedFile();
try {
rozpakuj(nazwaPliku, nazwaCelu);
}
catch (IOException ex) {
Logger.getLogger(Labirynt.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
}
public void rozpakuj(File source, File target) throws IOException {
try {
FileInputStream fis = new FileInputStream(source);
GZIPInputStream gis = new GZIPInputStream(fis);
FileOutputStream fos = new FileOutputStream(target);
byte[] buffer = new byte[1024];
int len;
while((len = gis.read(buffer)) != -1){
fos.write(buffer, 0, len);
}
//close resources
fos.close();
gis.close();
} catch (IOException e) {
}
tablica(target);
}//koniec rozpakuj
public void tablica (File target) throws FileNotFoundException, IOException{
BufferedReader reader = new BufferedReader(new FileReader(target));
int linie = 0,kolumny = 0;
while (reader.readLine() != null){
linie++;
}
reader.close();
BufferedReader reader2 = new BufferedReader(new FileReader(target));
kolumny = reader2.readLine().length();
reader2.close();
labirynt = new char[kolumny][linie];
wczytaj(target);
}
public void wczytaj(File target) throws FileNotFoundException, IOException{
BufferedReader odczyt = new BufferedReader(new FileReader(target));
int j=0;
String zdanie = odczyt.readLine();
//System.out.println(zdanie);
do{
for (int i=0;i<zdanie.length();i++){
labirynt[i][j] = zdanie.charAt(i);
//System.out.println("petla " + labirynt[i][j]);
}
zdanie = odczyt.readLine();
System.out.println(zdanie);
j++;
}while (zdanie != null);
szukacz();
}
public void szukacz() throws FileNotFoundException{
int x,y,xF=0,yF=0,xS=0,yS=0,xtemp,ytemp;
x = labirynt.length;
y = labirynt[0].length;
for (int j=0;j<y;j++){
for (int i=0;i<x;i++){
if (labirynt[i][j] == 'F'){
xF=i;
yF=j;
System.out.println("Punkt F znajduje sie " + xF + " " + yF);
continue;
}
else if (labirynt[i][j] == 'S'){
xS=i;
yS=j;
System.out.println("Punkt S znajduje sie " + xS + " " + yS);
continue;
}
else{
continue;
}
}
}//koniec szukanie punktow F i S
int[][] tablica = new int[x][y];
for (int j=0;j<y;j++){
for (int i=0;i<x;i++){
if (labirynt[i][j] == ' '){
tablica[i][j] = 0;
continue;
}
else if(labirynt[i][j] == 'X'){
tablica[i][j] = -1;
continue;
}
else if(labirynt[i][j] == 'F' || labirynt[i][j] == 'S'){
tablica[i][j] = 0;
}
else{
continue;
}
}
}//koniec przepisywania tablicy
/*System.out.println("Oto tablica przepisana /n");
for (int j=0;j<y;j++){
for (int i=0;i<x;i++){
System.out.print(tablica[i][j]);
}
System.out.println(" ");
}
System.out.println("Oto tablica przepisana - koniec /n");*/
int licznik = 1;
tablica[xS][yS] = 1;
Queue<Punkt> kolejka = new LinkedList<Punkt>();
Punkt punkt = new Punkt();
Punkt meta = new Punkt();
Punkt tymczas = new Punkt();
Punkt punkt2 = new Punkt();
meta.wspX = xF;
meta.wspY = yF;
punkt.wspX = xS;
punkt.wspY = yS;
//kolejka.offer(punkt);
do{
System.out.println("Punkt DO przerobienia " + punkt.wspX + " " + punkt.wspY);
if (tablica[punkt.wspX][punkt.wspY-1] == 0){
tablica[punkt.wspX][punkt.wspY-1] = tablica[punkt.wspX][punkt.wspY] + 1;
tymczas.wspX = punkt.wspX;
tymczas.wspY = punkt.wspY-1;
System.out.println("Punkty tymczas 1 " + tymczas.wspX + " " + tymczas.wspY);
kolejka.add(tymczas);
//continue;
}
if (tablica[punkt.wspX+1][punkt.wspY] == 0){
tablica[punkt.wspX+1][punkt.wspY] = tablica[punkt.wspX][punkt.wspY] + 1;
tymczas.wspX = punkt.wspX+1;
tymczas.wspY = punkt.wspY;
System.out.println("Punkty tymczas 2 " + tymczas.wspX + " " + tymczas.wspY);
kolejka.add(tymczas);
//continue;
}
if (tablica[punkt.wspX][punkt.wspY+1] == 0){
tablica[punkt.wspX][punkt.wspY+1] = tablica[punkt.wspX][punkt.wspY] + 1;
tymczas.wspX = punkt.wspX;
tymczas.wspY = punkt.wspY+1;
System.out.println("Punkty tymczas 3 " + tymczas.wspX + " " + tymczas.wspY);
kolejka.add(tymczas);
//continue;
}
if (tablica[punkt.wspX-1][punkt.wspY] == 0){
tablica[punkt.wspX-1][punkt.wspY] = tablica[punkt.wspX][punkt.wspY] + 1;
tymczas.wspX = punkt.wspX-1;
tymczas.wspY = punkt.wspY;
System.out.println("Punkty tymczas 4 " + tymczas.wspX + " " + tymczas.wspY);
kolejka.add(tymczas);
//continue;
}
System.out.println("dlugosc kolejki " + kolejka.size());
System.out.println("Punkt przerobiony " + punkt.wspX + " " + punkt.wspY);
punkt = kolejka.poll();
System.out.println("Punkt z kolejki " + punkt.wspX + " " + punkt.wspY);
System.out.println("dlugosc kolejki 22222222 " + kolejka.size());
punkt2 = kolejka.peek();
System.out.println("nastepny element " + + punkt2.wspX + " " + punkt2.wspY);
System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
}while (punkt.wspX != meta.wspX || punkt.wspY != meta.wspY);
for (int j=0;j<y;j++)
{
for (int i=0;i<x;i++){
System.out.print(tablica[i][j]);
}
System.out.println(" ");
}
Punkt[] sciezka = new Punkt[tablica[xF][yF]-2];
int[] sciezkaX = new int[tablica[xF][yF]-2];
int[] sciezkaY = new int[tablica[xF][yF]-2];
//System.out.println("wartosc knca sciezki to " + tablica[xF][yF]);
for (int k=tablica[xF][yF]-1;k>1;k--){
for (int j=0;j<y;j++){
for (int i=0;i<x;i++){
if (tablica[i][j] == k){
tymczas.wspX = i;
tymczas.wspY = j;
//System.out.println("Punkty tymczas sciezka " + tymczas.wspX + " " + tymczas.wspY);
sciezkaX[k-2] = tymczas.wspX;
sciezkaY[k-2] = tymczas.wspY;
labirynt[i][j] = '.';
}
}
//System.out.println(" ");
}
}
PrintWriter zapis = new PrintWriter("wynik.txt");
for (int j=0;j<y;j++){
for (int i=0;i<x;i++){
zapis.print(labirynt[i][j]);
}
zapis.println(" ");
}
zapis.println(sciezkaX.length);
for (int i=0;i<sciezkaX.length;i++){
zapis.println(sciezkaX[i] + " " + sciezkaY[i]);
}
zapis.close();
}//koniec szukacza
public static void main (String[] args) throws IOException{
new Labirynt();
System.out.println("Koniec");
}
}