Thread: Solving A Maze Using C Language!!!!

What if north, south, and west all have walls. Does the input file have 14 or E? I only see single-digit numbers in your example file is the reason I ask.

So does it give you coordinates? If so then why not make a 2D array and fill it with a certain character, say 'E' for empty. Then take all the coordinates and put the character 'F' in that spot in the array. Then when checking just plug your coordinates(your current location in the maze added with whatever amount you are moving in a certain direction) into the array and if it returns an E then that spot is empty, if it returns an F that spot is taken(a wall).

The 2D array is a good idea. You could make each element a bitfield. Say:

Code:

#define W_EAST  0x1
#define W_SOUTH 0x2
#define W_WEST  0x4
#define W_NORTH 0x8
#define CHECKED 0x10

Then, while reading the text file you just do array[row][column] = input_num;

Then start at the starting coordinates and move in all the possible directions. Something like:

Code:

void function(int cur_row, int cur_column)
{
  array[cur_row][cur_column] |= CHECKED;

  if(!(array[cur_row][cur_column] & N_WALL) && !(array[cur_row - 1][cur_column] & CHECKED))
    function(cur_row - 1, cur_column);

/* Same if(), but for the other 3 directions */
}

Do that for each direction and if the if() matches then call the function again recursively on the new row/column.

Then you also just need to check if the cur_row and cur_column match the destination coordinates.

Note: The CHECKED bit is only necessary if your maze can have more than one way to get to the same coordinate.

Imagine an 8-bit bitfield. While reading the input file you set each coordinate in the 2-d array to the value for that coordinate in the input field. So let's say maze[0][0] is 6. The maze[0][0] bitfield would look like 00000110.

So when you get ready to process coordinate 0,0 you grab that number and try going in each direction. The code example I gave is just a way of finding out if there's a wall in the direction you're trying to go. The & operator is bitwise AND. So let's say you try going east first. East is defined as 0x1. So you do maze[0][0] & W_EAST which is the same as:

00000110 (6) &
00000001 (1)
---------------
00000000 (0)

Since the result is 0 there's no wall to the east so you can go that way. If you tried south (defined as 0x2) you'd be doing:

00000110 (6) &
00000010 (2)
---------------
00000010 (2)

Since the answer isn't 0 there's a wall there so you can't go that way. So you have 4 if()s, one that tests each direction W_EAST (0x1), W_SOUTH (0x2), W_WEST (0x4), W_NORTH (0x8).

Hopefully that clears up some of it, but if you need more information on bitwise operators then check this out: http://www.eskimo.com/~scs/cclass/int/sx4ab.html