17
« Last post by Jeod on December 02, 2010, 05:26:18 PM »
/*
Solve the following 20x10 maze using an algorithm:
####################
## # ## ### #
## # ### # #
# # # ##### #######
# ## # ## # ##
# ## #### ## #### ##
# ## ## #### E
# ## #### ## #### ##
# #### ##
#S##################
The maze will be preset and not brought in as input. The solver should start as S and try to find a way to E. The program should mark the path it is
taking and also mark the paths that were incorrect.
The program should redraw the maze each time the solver takes a new step. In the solution, show a clean maze with a solution path that the solver found.
The program should have a main() function and at least one other function. You must also use arrays to store the maze. The masze must be solved in an
algorithm. Do not simply hardcode print statements. Use pointers for moving around the maze. Do not use subscription or indexing techniques.
*/
#include <stdio.h>
#include <windows.h>
#define FALSE 0
#define TRUE 1
#define COLS 20
#define ROWS 10
// Symbols:
// '.' = open
// '#' = wall
// 'S' = start
// 'E' = end
// '+' = path
// 'x' = bad path
char* maze[ROWS][COLS] = {
"#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#",
"#","#",".","#",".",".",".",".",".","#","#",".",".",".",".","#","#","#",".","#",
"#","#",".","#",".","#","#","#",".",".",".",".",".","#",".",".",".",".",".","#",
"#",".",".","#",".","#",".","#","#","#","#","#",".","#","#","#","#","#","#","#",
"#",".","#","#",".","#",".",".",".",".","#","#",".","#",".",".",".",".","#","#",
"#",".","#","#",".","#","#","#","#",".","#","#",".","#","#","#","#",".","#","#",
"#",".","#","#",".",".",".",".",".",".","#","#",".","#","#","#","#",".",".","E",
"#",".","#","#",".","#","#","#","#",".","#","#",".","#","#","#","#",".","#","#",
"#",".",".",".",".","#","#","#","#",".",".",".",".",".",".",".",".",".","#","#",
"#","S","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#",
};
void display_maze(void);
int find_path(int x, int y);
int main(void)
{
display_maze();
if ( find_path(0, 0) == TRUE )
{
printf("Success!\n");
Sleep(5000);
}
else
{
printf("Failed\n");
display_maze();
}
}
void display_maze(void)
{
printf("MAZE:\n");
for (int row = 0; row < ROWS; row++ )
{
printf("\n");
for (int col = 0; col < COLS; col++)
{
printf("%s", maze[row][col]);
}
}
printf("\n");
}
int find_path(int x, int y)
{
// If x,y is outside maze, return false.
if ( x < 0 || x > 9 || y < 0 || y > 19 ) return FALSE;
// If x,y is the goal, return true.
if ( *maze[y][x] == 'E' ) return TRUE;
// If x,y is not open, return false.
if ( *maze[y][x] != '.' && *maze[y][x] != 'S' ) return FALSE;
// Mark x,y part of solution path.
*maze[y][x] = '+';
// If find_path North of x,y is true, return true.
if ( find_path(x, y - 1) == TRUE ) return TRUE;
// If find_path East of x,y is true, return true.
if ( find_path(x + 1, y) == TRUE ) return TRUE;
// If find_path South of x,y is true, return true.
if ( find_path(x, y + 1) == TRUE ) return TRUE;
// If find_path West of x,y is true, return true.
if ( find_path(x - 1, y) == TRUE ) return TRUE;
// Unmark x,y as part of solution path.
*maze[y][x] = 'x';
return FALSE;
}
Find_Path is supposed to be the function that solves the maze. It looks for a path, and when it finds one, moves to that spot and marks the spot it was at with a +. It is recursive; the function should repeat itself until it finds the exit. On the chance the function runs into a wall, it should go back to the closest + sign that has a turn and try a new path.
Recent Posts
