DUzun's Web
Programare, proiecte personale, divertisment

/**

 * Se da un labirint sub forma de matrice cu m linii si n coloane.

 * Fiecare element al matricei reprezinta o camera a labirintului.

 * Într-una din camere, de coordonate x si y, se gaseste un om.

 * Se cere sa se gaseasca toate iesirile din labirint.

 *

 */

​

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

​

#define in_filename ("labirint.txt")

​

#define trap     ('*')

#define space    (' ')

#define me(x)    ((x)==trap||(x)=='x'||(x)=='X')

#define empty(x) ((x)==space||(x)=='0'||me(x))

​

#define _N     30

#define _UP    1

#define _RIGHT 2

#define _DOWN  4

#define _LEFT  8

​

typedef char tCell;

typedef tCell tRow[_N];

typedef tRow  tMap[_N];

typedef unsigned tSize;

typedef tSize tSol[100][2];

​

tMap map, dmap;

tSol sol;

tSize m,n;

int x,y; 

​

​

int  read_lab(char *fn);

void print_lab(tMap map);

int  ies(int x, int y, int k);

​

int main()

{

    clrscr();

​

    if(!read_lab(in_filename)) {

       printf("Nu exista fisierul %s!\n", in_filename);

       return 1;

    }

    printf("\nHarta (%dx%d):\n", n, m);

    print_lab(map);

    while(x < 0 || y < 0) {

       printf("\nPozitia (x, y):");

       scanf("%d %d", &x, &y);

       x--; y--;

       if(!empty(map[y][x]) || x >= n || y >= m) {

          printf("Perete!");

          x = -1;

       }

    }

​

    printf("\nHarta directiilor codificate hex:\n");

    print_lab(dmap);

    getch();

    printf("\nSolutii:\n");

​

    if(!ies(x,y,0)) {

       printf("\nNu sunt solutii :-(\n");

       getch();

    }

    return 0;

}

​

char tonr(tCell c) {

   if( 0 <= c && c <=  9) return c + '0';

   if(10 <= c && c <= 15) return c + 'A' - 10;

   return c;

}

​

void print_lab(tMap map) {

   tSize i,j;

   for(i = 0; i < m; i++) {

      for(j = 0; j < n; j++) printf("%c", tonr(map[i][j]));

      printf("\n");

   }

}

​

void tipar(int k) {

    int i;

    printf("--------------\n");

    for(i=0; i<k; i++) printf("(x,y)=(%d,%d)\n", sol[i][0]+1, sol[i][1]+1);

    getch(); 

}

​

void print_sol(int k)

{

   tSize i,j;

   for(i = 0; i < m; i++) for(j = 0; j < n; j++) if(empty(map[i][j])) map[i][j] = space;

   for(i = 0; i < k; i++) map[sol[i][1]][sol[i][0]] = trap;

   print_lab(map);

   getch(); 

}

​

int ies(int x, int y, int k)

{

    tCell c = dmap[y][x];

    int i, r = 1;

​

    if(!c) return 0; // Inkis

​

    sol[k][0] = x;

    sol[k][1] = y;

    if(x == 0 || x == n-1 || y == 0 || y == m-1) print_sol(k); // se poate tipar(k); // Am ajuns la margine

    else {

        for(i=0; i<k; i++) if(sol[i][0]==sol[k][0] && sol[i][1]==sol[k][1]) { r = 0; break; }

        if(r) {

            r = 0; // Presupunem ca nu sunt solutii

            k++;

            if( _LEFT  & c )  r |= ies(x-1,y  ,k);

            if( _RIGHT & c )  r |= ies(x+1,y  ,k);

            if( _UP    & c )  r |= ies(x  ,y-1,k);

            if( _DOWN  & c )  r |= ies(x  ,y+1,k);

        }

    }

    return r; // 0 - nu sunt solutii, 1 - sunt solutii

}

​

void norm_lab() {

   tSize i,j;

   tCell d = 0, a = 0;

   for(i = 0; i < m; i++) {

      a = 0;

      for(j = 0; j < n; j++) {

         if(a) map[i][j] = a; else if(!map[i][j]) a = '#'; // Completam liniile incomplete

         if(!empty(map[i][j])) d = 0;

         else {

           if( j == 0   || empty(map[i][j-1]) ) d |= _LEFT;

           if( j == n-1 || empty(map[i][j+1]) ) d |= _RIGHT;

           if( i == 0   || empty(map[i-1][j]) ) d |= _UP;

           if( i == m-1 || empty(map[i+1][j]) ) d |= _DOWN;

         }

         dmap[i][j] = d;

      }

   }

}

​

int read_lab(char *fn) {

   FILE* f;

   tRow  r;

   tSize i = 0;

   if(f = fopen(fn, "r")) {

       m = n = 0;

       x = y = -1;

       while(fgets(r, _N, f)) {

           i = 0;

           while(r[i] && r[i] != '\n' && r[i] != '\r') {

              if(me(r[i])) {

                 x = i;

                 y = m;

              }

              map[m][i] = r[i];

              i++;

           }

           map[m][i] = 0;

           if(i>n) n = i;

           m++;

           map[m][0] = 0;

       }

       fclose(f);

       norm_lab();

       return 1;

   } else return 0;

}

​