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