Suffolk University – College of Arts and Sciences Electrical and Computer Engine
ID: 3680562 • Letter: S
Question
Suffolk University – College of Arts and Sciences
Electrical and Computer Engineering Department
ENS 333 – Programming for Engineer
Maze Traversal: The following grid is an array representation of a maze. (Please explain)
The ‘#’ symbol represents the walls of the maze, and the period (.) represents squares in the possible path through the maze. S is the starting location (Start) and E is the ending location (Exit)
There is a simple algorithm for walking through a maze that guarantees finding the exit (if there is an exit). If there is no exit, you will arrive at the starting location again. Place your hand on the wall to your right and begin walking forward. Never remove you hand from the wall. If the maze turns to the right, you follow the wall to the right. As long as you do not remove your hand from the wall, eventually you will arrive at the exit of the maze. There may be shorter path than the one you have taken, but with this algorithm, you are guaranteed to find your way out of the maze.
Write a program that will get you out of a maze similar to the above pictured maze. Your program must read the maze from a file. Organize your program for easy debugging and understanding using functions, arrays and other features of the C programming language we have learned so far to accomplish the task.
Print out the maze after each step has been taken and mark each current position with the letter x.
Test your program for the case where there is an exit and for the case where this is no exit (in which case you will end up back at the starting location)
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#define DOWN 0
#define RIGHT 1
#define UP 2
#define LEFT 3
#define START_x 2
#define START_y 0
void mazeTraversal(char maze[12][12], int x, int y, int dir);
void printMaze(const char maze[][12]);
int validMove(const char maze[][12], int r, int c);
int cords(int x, int y);
int main()
{
char maze[12][12] =
{ { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1' },
{ '0', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '1' },
{ '1', '1', '1', '0', '1', '0', '0', '0', '0', '1', '0', '1' },
{ '1', '0', '0', '0', '0', '1', '1', '1', '0', '1', '0', '0' },
{ '1', '1', '1', '1', '0', '1', '0', '1', '0', '1', '0', '1' },
{ '1', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1' },
{ '1', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1' },
{ '1', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1' },
{ '1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' } },
mazeTraversal(maze, START_x, START_y, RIGHT);
return 0;
}
void mazeTraversal(char maze[12][12], int x, int y, int dir)
{
static int flag = 0;
maze[x][y] = 'X';
printMaze(maze);
if(cords(x,y) && x != START_x && y != START_y)
{
printf(" Maze successfully exited! ");
return;
}
else if( x == START_x && y == START_y && flag == 1)
{
printf(" Arrived back at the starting location. ");
return;
}
else
{
int move;
int count;
flag = 1;
for(move = dir, count = 0; count < 4; ++count, ++move, move %=4)
{
switch(move)
{
case DOWN:
if(validMove(maze, x+1, y) ) {
mazeTraversal(maze, x+1, y, LEFT);
return;
}
break;
case RIGHT:
if(validMove(maze, x, y+1) ) {
mazeTraversal(maze, x,y+1, DOWN);
return;
}
break;
case UP:
if(validMove(maze, x-1, y) ) {
mazeTraversal(maze, x-1,y, RIGHT);
return;
}
break;
case LEFT:
if(validMove(maze, x,y-1))
{
mazeTraversal(maze, x, y-1, UP);
return;
}
break;
}
}
}
}
int validMove(const char maze[][12], int r, int c)
{
return (r >=0 && r <= 11 && c >=0 && c <=11 && maze[r][c] != '1');
}
int cords(int x, int y)
{
if(( x == 0 || x == 11) && (y >=0 && y <= 11)) {
return 1;
}
else if(( y == 0 || y == 11) && (x >=0 && x <= 11) ) {
return 1;
}
else {
return 0;
}
}
void printMaze(const char maze[][12])
{
int x,y;
system("cls");
for(x =0; x< 12; x++)
{
for(y = 0; y < 12; y++)
{
printf("%c", maze[x][y]);
}
printf(" ");
}
printf(" Hit return to see next move");
getchar();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.