Escaping from the labyrinth

dezett's Avatar, Join Date: Dec 2011
Newbie Member
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;
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
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].
shabbir like this