1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Escaping from the labyrinth

Discussion in 'C' started by dezett, Dec 29, 2011.

  1. dezett

    dezett New Member

    Joined:
    Dec 29, 2011
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    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;
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    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].
     
    shabbir likes this.

Share This Page