Optymalizacja programu

0

Prosze o pomoc w optymalizacji programu. Wyszukuje on najkrotsza droge wyjscia z labiryntu ktorego maksylamny rozmair to 100x100

Program ma otrzymywać na wejściu dwie liczby (całkowite dodatnie) n i m oznaczajace wymary labiryntu (tablicy) i cztery liczby całkowite (dwie pierwsze określają punkt początkowy w labiryncie, a dwie następne wyjście), a następnie n linijek po m liczb ze zbioru {-5,-1,0}, przy czym liczba -5 może wystąpić raz lub dwa razy w n linijkach (jedna z nich to punkt początkowy, a druga wyjście), gdzie -1 oznacza ścianę, a liczba 0 oznacza korytarz. Przyjąć, że 0 ≤ m, n ≤ 100. W labiryncie można poruszać się w czterech kierunkach: w górę, w dól, w prawo lub w lewo - nie można poruszać się po skosie. Wynikiem działania programu powinna być linijka zawierająca

liczbę będącą długością najkrótszej drogi z punktu poczatkowego do wyjścia, o ile istnieje,
łańcuch znaków: NIE WYJDZIESZ ;( , jeśli taka droga nie istnieje.
Uwaga !!! Nie wolno używać pojemników z biblioteki standardowej (vector, set, map, list, queue) oraz znaków '[' i ']' w kodzie programu.

Wejście

W pierwszej linii standardowego wejścia znajdują się dwie liczby całkowite n i m (odzielone spacją) określające wymiar tablicy (n wierszy i m kolumn). W drugiej linii, kolejno, znajdują się współrzędne (wiersz kolumna) punktu początkowego i wyjścia odzielone spacjami. Współrzędne wyjścia mogą wykraczać poza wymiar tablicy. Kolejne n linii zawierają m liczb odzielonych spacjami ze zbioru {-5,-1,0}.

Wyjście

Linia zawierająca

liczbę będącą długością najkrótszej drogi z punktu poczatkowego do wyjścia, o ile istnieje,
łańcuch znaków: NIE WYJDZIESZ ;( , jeśli taka droga nie istnieje.
Przykłady:

Dla danych wejściowych:

6 20
5 2 2 17
0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 0 0 0
0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 -1 -1 -5 0 0
0 -1 0 0 -1 0 0 0 0 -1 0 0 -1 0 0 0 0 -1 0 0
0 0 0 0 0 0 -1 0 0 -1 0 0 0 -1 0 0 0 0 0 0
0 0 -5 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0
Dla danych wejściowych:

5 8
4 0 0 7
0 0 -1 -1 -1 -1 -1 -5
-1 0 0 -1 0 -1 0 0
0 -1 0 0 -1 -1 -1 -1
0 0 0 -1 -1 -1 0 0
-5 -1 0 -1 0 -1 0 -1
poprawną odpowiedzią jest:

22
poprawną odpowiedzią jest:

NIE WYJDZIESZ ;(

#include <stdio.h>
#include <stdlib.h>
int result;
int fak=10000;
int **lab = (int**) malloc(100 * sizeof *lab);

int backtracking(int x1, int y1, int x2, int y2,int cnt)
{cnt++;
if(x1==x2&&y1==y2) //sprawdza dopoki sprawdzany bedzie wspolrzedna wyjscia
    {  if(cnt<fak)fak=cnt;
        result++;
        return 0;
    }
*(*(lab + x1) + y1)=1;
if(*(*(lab + x1+1) + y1)==0){
    backtracking(x1+1,y1,x2,y2,cnt);}
if(*(*(lab + x1-1) + y1)==0){
    backtracking(x1-1,y1,x2,y2,cnt);}
if(*(*(lab + x1) + y1+1)==0){
    backtracking(x1,y1+1,x2,y2,cnt);}
if(*(*(lab + x1) + y1-1)==0){
    backtracking(x1,y1-1,x2,y2,cnt);}
*(*(lab + x1) + y1)=0;

return 0;
}

int main()
{

int n,m,x1,y1,x2,y2;
  scanf("%d %d",&n,&m);     //pobieranie rozmiaru labiryntu
for (int i =0; i< n+2; i++){
 *(lab+i) = (int*) malloc((m+2)*sizeof(**lab));
}
for(int i=0;i<=n+1;i++)         //
{
    *(*(lab + i)) =-1;
    *(*(lab + i) + m+1)=-1;
}                                                //przygotowywanie labiryntu. Wokol labiryntu jest tworzony "mur" z '-1' zeby za kazdym razem jie trzeba bylo sprawdzc czy nie         wychodzimy poza tablice

for(int j=0;j<=m+1;j++)
{
    *(*(lab)+j)=-1;
    *(*(lab+n+1)+j)=-1;
}                               //
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);    //pobieranie wspolrzecnych wejscia do labiryntu (x1,y1) i wyjscia (x2,y2)
if((((x1>=n))&&(y1>=m))||(((x2>=n))&&(y2>=m)))
    printf("NIE WYJDZIESZ ;(\n");
    else{
    for(int i=1;i<=n;i++)                              //pobieranie komorek labiryntu. jesli komorka ma wartosc '0' to mozna przejsc, jeli '-1' to jest to sciana
        for(int j=1;j<=m;j++)
            scanf("%d",*(lab + i) + j);

      *(*(lab+x1+1)+y1+1)=0;
      *(*(lab+x2+1)+y2+1)=0;
result=0;
backtracking(x1+1,y1+1,x2+1,y2+1,0);

if(result)                           //jesli jesst conajmniej jedna droga wyjscia to wtedy wypisuje najkrotsza
    printf("%d\n",fak);
else
    printf("NIE WYJDZIESZ ;(\n");

for (int i = 0; i < n+2; i++){
    free(*(lab+i));
 }
 free(lab);

return 0;}
}
0

if(((
masacre! słyszałeś ty o operatorze []?

zamiast

*(*(lab + i)) =-1;

pisz

*lab[i] =-1;

albo

lab[i][0] = -1;

zamiast

*(*(lab + i) + m+1)=-1;

pisz

lab[i][m+1]=-1;
0

Uwaga !!! Nie wolno używać pojemników z biblioteki standardowej (vector, set, map, list, queue) oraz znaków '[' i ']' w kodzie programu.

no to

lab<:i:><:m+1:>=-1;
0

Usunięte

0

Przykro mi, ale z tego kodu nijak nie da się odczytać jakim algorytmem szukasz tego wyjścia z labiryntu więc trudno cokolwiek zaproponować. Uzywasz tu Dijkstry? Bellmana Forda? BFS + A*?

0

usuniete

0

Czyli zrobiłeś DFSa rekurencyjnego i to takiego który testuje wszystkie możliwe kombinacje. Nie wiem czy dało się to zrobić mniej optymalnie :P
To w ogóle daje ci poprawne rozwiązanie? Bo mam wątpliwości. DFS ani BFS nie znajdują ci wcale optymalnej ścieżki, może się ona różnić od optymalnej prawie dwukrotnie...

  1. Wiesz ze da sie to zrobić iteracyjnie równie łatwo? To juz za pewne daloby ci spore przyspieszenie
  2. Ten sam problem można rozwiązać (i to uzyskując zawsze poprawne rozwiązanie!) za pomocą banalnego algorytmu w czasie O(n^3). Google: algorytm bellmana forda...
0

Nie potrafie tego zrobic metoda bellmana bo nie umiem jesczze grafow. W jaki sposob zrobic to iteracyjnie? myslalem o tym jak usprawnic ta funkcje zeby nie sprawdzac wszytskich sciezek ale nie udalo mi sie nic wymyslic i dlatego napisalem ten temat.

0

Iteracyjnie?

//lista to jakaś implementacja listy
lista.add(pozycja startowa);
while(!lista.empty()){
  element = lista.pop();
  sprawdzamy czy element = koniec labiryntu i jeśli tak to kończymy pracę
  sprawdzamy wszystkie kierunki i jeśli jakis nam pasuje to:
  oznacz ten kierunek jako już "wykorzystany" (jeśli pominiesz ten krok to rozwiązanie uzyskane będzie optymalne ale będzie działało, tak jak twój algorytm, w czasie O(n!))
  wrzuc ten kierunek do listy
}

Ale użycie takiego BFSa/DFSa nie da ci poprawnego rozwiązania. Twój algorytm daje poprawne rozwiązanie tylko dlatego że pozwalasz na wielokrotne przechodzenie przez te same wierzchołki i to ci daje kosmiczną złożoność.
Zamiast więc płakać że "nie umiem grafów" napisz po prostu bellmana forda.

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