3 replies to this topic

[dezett]

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.

FIFO queue:

#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;

}

Any advice would be appreciated.

Edited by dezett, 29 December 2011 - 09:37 AM.

[dargueta]

1) You must set begin and end in your FIFOQueue to 0 in the constructor. No one will do this for you.
2) With the first example I get a segmentation fault; in in() e gets up to 16858. Your problem:

You enqueue stuff and dequeue it, which is fine, but you need to shift everything down once in a while. When you dequeue, you move your begin index up one. When you enqueue, you append. Now you can keep enqueueing and then dequeueing items such that the queue itself stays the same length, but your begin and end pointers keep going up and up until they run off the end of the memory you allocated. Though it's inefficient, I suggest you do something like this:

int *out()
{
    if( nitems == 0 )
        return NULL;
        
    int *retval = buffer[0];
    
    for( int i = 0; i < nitems - 1; ++i )
        buffer[i] = buffer[i + 1];
        
    --nitems;
    return retval;
}

You'd have to add a field called nitems that keeps track of the number of items in the queue, but begin and end wouldn't be necessary.

Edited by dargueta, 29 December 2011 - 02:16 PM.
Forgot something

[dezett]

Thanks for the reply. I changed in() and out() as you have suggested. Though the program works, it still returns no answer for the 1st labyrinth and a bad answer for the 2nd.

The code now:

#include <stdio.h>

#include <cstdlib>


struct FIFOQueue {

    int** buffer;

    int nitems;

	

	FIFOQueue(int n) 

	{

		buffer = (int**) malloc(sizeof(int*)*n);

	}


	void in(int* e)

	{

		*(buffer + nitems) = e;

		nitems++;

	}


	int *out()

        {

                if( nitems == 0 )

                return NULL;

        

                int *retval = buffer[0];

    

                for( int i = 0; i < nitems - 1; ++i )

                     buffer[i] = buffer[i + 1];

        

                --nitems;

                return retval;

        }

};


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.nitems = 0;

		

		// 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.nitems > 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 adding 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.nitems - 1);

					counter++;

				}

			} else { // if the queue is empty printf and break;

				printf("You won't escape");

				break;

			}

		}

    }

	return 0;

[dargueta]

Put parentheses around all of your conditions. Sometimes that's the problem.

((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))

And why are you using or instead of ||? Shouldn't you have to include iso646.h for that?