programowanie

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
/* **************************************
 * Autorem programu jest:
 *         Piotr KARNY
 * **************************************/

/* Lista punktów ostatecznych */
typedef struct ostateczne
{
  int x;
  int y;
  struct ostateczne *next;
  struct ostateczne *prev;
}*wskListy_o,elListy_o;
/* Lista punktów uzytych */
typedef struct uzyte
{
  int x;
  int y;
  struct uzyte *next;
  struct uzyte *prev;
}*wskListy,elListy;

/* Zmienne globalne */
int N=0,
    M=0,
    found = 0;
wskListy pierwszy = NULL, 
         ostatni = NULL;
wskListy_o pierwszy_o = NULL,
           ostatni_o = NULL;
/* Preprocesor */
int przechodz(int **tab, int x1,int y1, int x2,int y2);
void animacja(wskListy iterator, int **tab);
void animacja2(wskListy_o iterator, int **tab);
void dodaj(int x, int y);
int sprawdz(int iks, int igrek);
void usun_liste(wskListy iterator);
void usun_liste2(wskListy_o iterator);
void wypisz_liste();
void odwracanie(wskListy iterator);
/*************************
 * Główna część programu *********************************************************************************************************
 *************************/

int main(int argc, char *argv[])
{
  int **plansza;
  FILE *plik;
  char linia[250], c;
  int znak=0, temp=0, i=0, j=0, x, y, xk, yk, ok;
  
  plik = fopen("labirynt.txt", "r");
  
  while(fgets(linia, 240, plik) != NULL)
  {
    M++;                  
  }
  
  fseek(plik,0,0);
  while(fscanf(plik, "%d", &znak)!= EOF)
  {
   temp++;                  
  }
  N = temp/M;
 
  printf("Ilosc wierszy: %d\nIlosc kolumn: %d\n", M, N);
  
  /* Rezerwowanie pamieci */
  plansza = (int**)malloc(sizeof(int*)*M);
  for(i=0;i<M;i++) plansza[i] = (int*)malloc(sizeof(int)*N);
  /* Koniec rezerwowania pamieci */
  
  fseek(plik,0,0);
  /* Ładowanie pól do tablicy */
  for(i=0; i<M; i++)
  {
   for(j=0; j<N; j++)
   {
    fscanf(plik, "%d", &znak);
    plansza[i][j] = znak;   
   }
  }
  /* Rysowanie labiryntu */
  printf("Pobrany z pliku labirynt wyglada tak:\n");
  for(i=0; i<M; i++)
  {
   for(j=0; j<N; j++)
   {
    if(plansza[i][j] == 0)
    printf("%c",219);
    if(plansza[i][j] == 1)
    printf("%c",176);
    if(plansza[i][j] == -1)
    printf("#");        
   }
   printf("\n");         
  }
  /* Pobieranie punktów startu i mety */
  do {
     printf("Podaj wspolrzedne startu [wiersz kolumna]:");
     scanf("%d %d", &x, &y);
     if(x>=M || x<0 || y>=N || y<0)
     { 
       ok = 0;
       printf("ERROR: Podane punkty sa poza zakresem!\n\n");
     }
     else if(plansza[x][y]==1)
     { ok =1; }
     else
     { 
     printf("ERROR: Podany punkt znajduje sie w scianie!\n\n"); 
     ok = 0;
     }
  }while(ok != 1);
  
  do {
     printf("Podaj wspolrzedne konca [wiersz kolumna]:");
     scanf("%d %d", &xk, &yk);
     if(xk>=M || xk<0 || yk>=N || yk<0)
     { 
       ok = 0;
       printf("ERROR: Podane punkty sa poza zakresem!\n\n");
     }
     else if(plansza[xk][yk]==1)
     { ok =1; }
     else
     { 
     printf("ERROR: Podany punkt znajduje sie w scianie!\n\n"); 
     ok = 0;
     }
  }while(ok != 1);
  
  system("cls");
  printf("Labirynt z zaznaczonymi punktami:\n");
  for(i=0; i<M; i++)
  {
   for(j=0; j<N; j++)
   {
    if((i == x && j == y)) printf("S");
    else if(i == xk && j == yk) printf("M"); 
    else if(plansza[i][j] == 0)
    printf("%c",219);
    else if(plansza[i][j] == 1)
    printf("%c",176);        
   }
   printf("\n");         
  }
  fclose(plik);
  
 if(przechodz(plansza, x, y, xk, yk)==1) printf("Znaleziono droge!\n"); else {printf("Nie znaleziono drogi!\n");}
 odwracanie(ostatni); /* odwócenie drogi zeby pokazac poprawnie */
 printf("Aby zobaczyc animacje procesu szukania drogi nacisnij dowolny klawisz na klawiaturze.");
 getch();
 animacja2(pierwszy_o, plansza);
 printf("Aby zobaczyc jak po kolej zapisane zostaly punkty na liscie nacisnij dowolny klawisz na klawiaturze.");
 getch();
 animacja(pierwszy, plansza);
 printf("Aby zobaczyc animacje poprawnej drogi nacisnij dowolny klawisz na klawiaturze.");
 getch();
 animacja2(pierwszy_o, plansza);
 Sleep(200);
 /* Usuwanie list */
  usun_liste(pierwszy);
  usun_liste2(pierwszy_o);
  /*  Zwalnianie pamieci tablicy dynamicznej*/
  for(i=0; i<M; i++) free(plansza[i]);
  free(plansza);
  /* Koniec zwalniania pamieci */
  
  system("PAUSE");	
  return 0;
}
/***********
 * Funkcje ***********************************************************************************************************************
 ***********/
int przechodz(int **tab, int x1,int y1, int x2,int y2)
{
    dodaj(x1,y1);

    if(!(x1 == x2 && y1 == y2))
    { 
          
          /* prawo */
          if(x1>=0 && y1+1>=0 && x1<M && y1+1<N && tab[x1][y1+1] == 1 && sprawdz(x1,y1+1)==0)
          {
                    
                    if (przechodz(tab, x1, y1+1,x2,y2)==1) return 1; /* zwracanie wartosci do funkcji wyzej w rekurencji */
          }
          /* dol */
          if(x1+1>=0 && y1>=0 && x1+1<M && y1<N && tab[x1+1][y1] == 1 && sprawdz(x1+1,y1)==0)
          {
                     if(przechodz(tab, x1+1, y1,x2,y2)==1) return 1; /* zwracanie wartosci do funkcji wyzej w rekurencji */
          }
          /* lewo */
          if(x1>=0 && y1-1>=0 && x1<M && y1-1<N && tab[x1][y1-1] == 1 && sprawdz(x1,y1-1)==0)
          {
                     if(przechodz(tab, x1, y1-1,x2,y2)==1) return 1; /* zwracanie wartosci do funkcji wyzej w rekurencji */
          }
          /* gora */
          if(x1-1>=0 && y1>=0 && x1-1<M && y1<N && tab[x1-1][y1] == 1 && sprawdz(x1-1,y1)==0)
          {
                     if(przechodz(tab, x1-1, y1,x2,y2)==1) return 1; /* zwracanie wartosci do funkcji wyzej w rekurencji */
          }
          else
          {
              found = 0;
              return 0;  /*nie znaleziono drogi */
          }

         
    }
    else
    {
         found = 1; 
        return 1; /* znaleziono droge; */
    }
}
/* funkcja 'animacja' rekurencyjnie pokazuje przebieg drogi */
void animacja(wskListy iterator, int **tab)
{
   int i, j;
   system("cls");
   if(iterator)
   {
     for(i=0;i<M;i++)
     {
      for(j=0;j<N;j++)
      {
        if(iterator->x == i && iterator->y == j) printf("*");
        else if (tab[i][j] == 0) printf("%c",219);
        else if (tab[i][j] == 1) printf(" ");
        
      }
      printf("\n");     
     }
     printf("x = %d, y = %d", iterator->x,iterator->y);
     Sleep(432);
     animacja(iterator->next, tab);
   }
}
/* funkcja 'animacja2' rekurencyjnie pokazuje przebieg odwróconej drogi */
void animacja2(wskListy_o iterator, int **tab)
{
   int i, j;
   system("cls");
   if(iterator)
   {
     for(i=0;i<M;i++)
     {
      for(j=0;j<N;j++)
      {
        if(iterator->x == i && iterator->y == j) printf("*");
        else if (tab[i][j] == 0) printf("%c",219);
        else if (tab[i][j] == 1) printf(" ");
        
      }
      printf("\n");     
     }
     printf("x = %d, y = %d", iterator->x,iterator->y);
     Sleep(432);
     animacja2(iterator->next, tab);
   }
}
/* funkcja 'dodaj' dodaje podany w parametrze punkt na poczatek listy 'uzyte' */
void dodaj(int x, int y)
{
     wskListy el;
     
     el = (wskListy)malloc(sizeof(elListy));
     el->x = x;
     el->y = y;
     el->next = pierwszy;
     el->prev = NULL;

     if(pierwszy)
     {
       pierwszy->prev=el;
     }
     
     if(ostatni == NULL)
     {
       ostatni = el;
     }
     
     pierwszy = el;
}
/* funkcja 'sprawdz' sprawdza czy dany podany punkt istnieje na liscie */
int sprawdz(int iks, int igrek)
{
   wskListy iterator = pierwszy;
   int jest = 0; 
   if(iks<M && igrek<N && iks>=0 && igrek>=0)
   {
    while(iterator)
    {
     if(iterator->x == iks && iterator->y == igrek) jest = 1;
     iterator = iterator->next;
     }
  }
  else
  { 
      jest = 1;
  }
   return jest;
}
/* funkcja 'usun_liste' rekurencyjnie usuwa liste 'uzyte' */
void usun_liste(wskListy iterator)
{
     if(iterator)
     {
       if(iterator->next) iterator->next->prev = NULL;
       usun_liste(iterator->next); /* rekurencja */
       iterator->next = NULL;
       pierwszy=NULL;
       if(ostatni) ostatni = NULL;
       free(iterator);
     }
     
}
/* funkcja 'usun_liste2' rekurencyjnie usuwa liste 'ostateczne' */ 
void usun_liste2(wskListy_o iterator)
{
     if(iterator)
     {
       if(iterator->next) iterator->next->prev = NULL;
       usun_liste2(iterator->next); /* rekurencja */
       iterator->next = NULL;
       pierwszy=NULL;
       if(ostatni) ostatni = NULL;
       free(iterator);
     }
     
}
/* funkcja 'wypisz_liste' mozna ja umiescic w dowolnym miejscu w programie. Pomocna w sprawdzeniu zawartosci listy 'uzyte' */
void wypisz_liste()
{
 wskListy iterator = pierwszy;

 while(iterator)
 {
  printf("lista x = %d ; y = %d \n", iterator->x, iterator->y);
  iterator = iterator->next;               
 }
}
/* funkcja 'odwracanie' rekurencyjnie przepisuje liste punktów na drugą listę w odwrotnej kolejnosci */
void odwracanie(wskListy iterator)
{
    wskListy_o el;
     /* poruszamy sie w tył! */
    if(iterator)
    {
     el = (wskListy_o)malloc(sizeof(elListy_o));
     el->x = iterator->x;
     el->y = iterator->y;
     el->next = NULL;
     el->prev = ostatni_o;

     if(ostatni_o)
     {
       ostatni_o->next=el;
     }
     
     if(pierwszy_o == NULL)
     {
       pierwszy_o = el;
     }
     
     ostatni_o = el; 
     
     odwracanie(iterator->prev); /* rekurencja */         
    }   
}

Uwagi do działania programu labirynt:
 - podając punkty najpierw podajemy numer wiersza, nastepnie po spacji (lub [enter]) podajemy numer kolumny
 - numeracja wierszy i kolumn zaczyna się od 0 (np 0 0 jest punktem w lewym górnym narożniku labiryntu)
 - przy wiekszych labiryntach (>50x50) labiryntach animacje mogą trwać dość długo

Piotr Karny