Witam,
mam napisać program, który sprawdza czy labirynt ma wyjście.
Labirynt jest prezentowany przez tablice [10][10] o wejsciu w (0,0) i wyjsciu w (9,9)
Gdzie 'X' to ścianki a '0' to 'korytarz'
Czy jest jakiś prosty sposób , aby stwierdzić czy labirynt ma wyjście?
prosze o wskazówki
Poszukaj sobie algorytmu backtracingu, ew. klasyczny algorytm: idziesz zawsze z prawa reka dotykajaca sciany :)
Ślęcze nad tym algorytmem i wymyśliłem takie coś:
#include<iostream.h>
#include<string.h>
using namespace std;
int main()
{
int labirynt[11][11];
char lab;
string labir;
while(cin>>labir) //dopóki wczytuje labirynty
{
cout<<labir[0]<<endl; //wczytaj labirynt
int x=0,y=0;
for(x=0;x<10;x++) //wczytuje do tablicy labirynt ze stringa
{
for(y=0;y<10;y++)
{
if(labir[x*10+y]=='X')
{
labirynt[x][y]=1; //jesli sciana to 1
}
if(labir[x*10+y]=='O') //jesli korytarz to 0
{
labirynt[x][y]=0;
}
}
}
int poz=0,wiersz=0;
int iks=0,igrek=0;
while((iks!=9)&&(igrek!=9)) //dopóki nie jest na wyjsciu
{
if(igrek-1>-1)
{
if(labirynt[iks,igrek-1]==0)--igrek; //wprawo
}else if(iks+1<10)
{
if(labirynt[iks+1,igrek]==0)++iks; //front
}else if(igrek+1<10)
{
if(labirynt[iks,igrek+1]==0)++igrek; //w lewo
}else
{
cout<<'0'<<endl;break; /jesli brak wyjscia
}
}
cout<<'1'<<endl; //jesli jest wyjscie
}
return 0;
}
Ale nie działa [wstyd] </cpp>
Nie kumam za bardzo tego twojego wczytywania labiryntow :/ Wez wczytaj najpierw sensownie ten labirynt, albo wpisz go na razie na sztywno (do testow) i sprawdz najpierw czy na danej tablicy znajdzie wyjscie.
Z tekiej formy mam wczytać labirynty:
LAB 1: OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
LAB 2 OOOOOOOOOOXXXXXXXXXXOOOOOOOOOOXXXXXXXXXXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
Następnie zamieniam to sobie na tablicę 10 na 10. i tam gdzie jest X to zamieniam na 1 , a jak O to wypisuje 0.
Bardzo proszę o pomoc :(
Przyklad wczytania dla pliku
dane.txt
OOOOOOOOOOXXXXXXXXXXOOOOOOOOOOXXXXXXXXXXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
int labirynt[10][10];
//wczytanie
ifstream plik("dane.txt");
int i = -1;
while(!plik.eof() && ++i<100)
labirynt[i/10][i%10] = plik.get() == 'O' ? 0:1;
plik.close();
//sprawdzenie
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < 10; j++)
cout << labirynt[i][j];
cout<<endl;
}
cin.get();
return 0;
}
Dzieki :)
teraz tylko zbadać czy ma wyjście dany labirynt.
Szczarze nie umiem tego, robie to chyba cały dzień i nic :(
bez rezultatów [wstyd]
No to tak jak mowilem. Dla malego labiryntu mozesz zrobic tak, jak z ta reka. Czyli zaczynasz od miejsca gdzie jest wejscie i posuwasz sie zawsze w prawo - w sensie punktu widzenia oczywiscie. Czyli cos takiego:
Proponuje na poczatek napisac sobie metody, ktore pomoga Ci obracac sie w prawo z jakiegos miejsca, robic krok naprzod, itp - tak, zeby to wszystko dzialo sie na tablicy i zapamietywalo aktualny 'punkt widzenia' - czyli obrot i miejsce przebywania.
Dla tak malego algorytmu moze nawet rekurencja być - wiem że to bardzo pamięć wcina ale na upartego.
Możesz w ten sposób zrobic to tak że 0 to ściana, 1 to ścieżka "dziewicza", a np 2 to ścieżka przebyta - jeśli bedziesz na swej drodze spotykał sciezke przebyta tzn że tą częśc labiryntu już przebyłeś możesz ją wyłaczyć z trasy i zacząć ruch od punktu gdzie spotkałeś się z przbyta scieżką ale juz nie mozesz tam wstąpić.
Ale ogólnie pomysl z prawą ręką mi się tez podoba. Powodzenia.
wpisz do komurki[0][0] liczbe 1
do każdej sąsiedniej (ale pustej) 2
i ak dalej
po zapełnienui całej tablicy wystarczy odszukać szereg 1...N