Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Escaping from the labyrinth (http://www.go4expert.com/forums/escaping-labyrinth-t27482/)

dezett 29Dec2011 23:19

Escaping from the labyrinth
 
Hello.
I'm having troubles with getting a program to work.
It has to return how many steps is takes to get out of the labyrinth or a sentence "You won't escape".
The user types in: sizes of the labyrinth x * y, the positions of start and exit and the labyrinth itself ( where -5 is start/exit, -1 is a wall and 0 is a corridor).
For example:
3 5
0 0 2 4
-5 0 0 0 0
0 -1 -1 -1 0
0 0 0 0 -5

The program should return: 6

I have written a program. It uses a FIFO queue. It seems to work but when i typed:
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

The program has crushed.
Compiling shows no errors.

Typed in:
5 5
2 4 4 2
-1 0 0 0 0
-1 -1 -1 -1 0
0 -1 -1 -1 -5
-1 0 0 0 0
-1 -1 -5 0 -1

Program returned 6, while it should 4.
Something's wrong.
Any help would be appreciated.

Code:

#include <stdio.h>
#include <cstdlib>

struct FIFOQueue {
    int** buffer;
    int begin, end;
       
        FIFOQueue(int n)
        {
                buffer = (int**) malloc(sizeof(int*)*n);
        }

        void in(int* e)
        {
                *(buffer + end) = e;
                end++;
        }

        int* out()
        {
                return *(buffer + (begin++));
        }

        void flush()
        {
        begin = 0, end = 0;
    }
};

int main()
{
        int n, m; // sizes of the labyrinth
        int **t;
       
        scanf("%d %d", &n, &m);
        n=n+2;
        m=m+2;
       
        t = (int**) malloc(n*sizeof(int*));
       
        for(int i=0;i<n;i++)
        {
                *(t+i) = (int*) malloc(m*sizeof(int));
        }
        // surrounding the labyrinth with -1s
        for(int i=0;i<m;i++)
        {
                *(*(t+0)+i) = -1;
                *(*(t+n-1)+i) = -1;
        }
       
        for(int i=0;i<n;i++)
        {
                *(*(t+i)+0) = -1;
                *(*(t+i)+m-1) = -1;
        }
       
        // getting the positions of start & exit
        int s1, s2, e1, e2;
        scanf("%d %d %d %d", &s1, &s2, &e1, &e2);
        s1 = s1+1;
        s2 = s2+1;
        e1 = e1+1;
        e2 = e2+1;
        // checking if start/exit outside the labyrinth
        if(e1 < 0 or e2 < 0 or e1 > n-2 or e2 > m-2 or s1 < 0 or s2 < 0 or s1 > n-2 or s2 > m-2)
        {
                printf("You won't escape");
        } else { // getting the labyrinth
                for(int i=1;i<n-1;i++)
                {
                        for(int j=1;j<m-1;j++)
                        {
                                scanf("%d", *(t+i)+j);
                        }
                }
               
                // creating the queue
                FIFOQueue queue(n * m);
                queue.flush();
               
                // adding the start to the queue
                int *start = *(t+s1)+s2;
                *start = -4;

                queue.in(start);

                int counter = 0;
                int *equidistance = start; //pointer which says where the zone of equal distances ends
               
                while(1)
                {
                        if(queue.end - queue.begin > 0) // if queue not empty
                        {
                                int* element = queue.out();

                                *element = 2;

                                int* left = element - 1;
                                int* right = element + 1;
                                int* up = element - m;
                                int* down = element + m;

                                if(*left == -5 or *right == -5 or *up == -5 or *down == -5) // if exit break
                                {
                                        counter++;
                                        printf("%d", counter);
                                        break;
                                }

                                if(*left != 2 or *left != -1) // checking if a corridor or exit and aading to the queue
                                {
                                        queue.in(left);
                                }
               
                                if(*right != 2 or *right != -1)
                                {
                                        queue.in(right);
                                }
               
                                if(*up != 2 or *up != -1)
                                {
                                        queue.in(up);
                                }
               
                                if(*up != 2 or *down != -1)
                                {
                                        queue.in(down);
                                }
       
                                if(element == equidistance)  // increasing the distance
                                {
                                        equidistance = *(queue.buffer + queue.end - 1);
                                        counter++;
                                }
                        } else { // if the queue is empty printf and break;
                                printf("You won't escape");
                                break;
                        }
                }
    }
        return 0;


xpi0t0s 31Dec2011 04:45

Re: Escaping from the labyrinth
 
This program would be easier to read if you used array semantics instead of pointers. So replace this:
Code:

*(*(t+0)+i) = -1;
with whichever of the following two statements is correct:
Code:

t[0][i] = -1;
t[i][0] = -1;

and repeat throughout the program.

Don't do this:
Code:

if(e1 < 0 or e2 < 0 or e1 > n-2 or e2 > m-2 or...
Just learn that || means OR and use || instead of some dumb #define that makes the program look more like Pascal or whatever (because it doesn't, and just ends up making your code harder to read). This code is perfectly readable:
Code:

if(e1 < 0 || e2 < 0 || e1 > n-2 || e2 > m-2 ||...
If your program has crashed then there's a good chance you've stuffed up your memory usage. So for example you might have confused:
Code:

int t[6][20];
with
Code:

int t[20][6];
If you really want to manage your arrays at a low level instead of using [][] syntax then just allocate 6*20 ints and address them with x+y*20 syntax instead of all this *(t+this)+that+(*)the**(*)+other*(*) or whatever shit you have to type to do what the compiler does automatically for you when you do t[a][b].


All times are GMT +5.5. The time now is 16:58.