Czy labirynt ma wyjście?

0

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

0

Poszukaj sobie algorytmu backtracingu, ew. klasyczny algorytm: idziesz zawsze z prawa reka dotykajaca sciany :)

0

Ś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>

0

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.

0

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 :(

0

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;
}
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]

0

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:

  1. Czy da sie pojsc w prawo
    1a. Tak
    2a. obrot w prawo
    3a. krok naprzod
    4a. powrot do punktu 1.
    1b. obrot w prawo
    2b. powrot do punktu 1.

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.

0

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.

0

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0