Return to the Top of Page, First Page, or Veteran Problem Set.
Your goal is to discover how many steps it takes to walk through a closed maze. A step is defined as the process of moving from a space to another empty space. Steps can only be made vertically and horizontally (no diagonal moves allowed). The maze will not have any places where more than one choice can be made. The maze will not have any dead ends.
The column on the left, below, is some sample input for your program. Notice that mazes are separated by a blank line and that mazes can contain a space where no valid path exists. Exactly one blank line will separate mazes. End-of-file checking should be used to determine if there are no more mazes. A # (number sign) is used to indicate a wall of the maze. A . (period) is used to indicate where a empty space in the maze exists.
Entry into the maze will always be from a space on the left side of the maze. There will always be only one (1) space on the left side of the maze. Exit will always be on the right side. All mazes will be solvable in exactly one way. Mazes may have more than one open space on the right side.
Example Maze:
################## #.#............... ###.############## #.#......#####...# ########.#...#...# #.....##.#.#.###.# #.###.##.#.#...#.# #..##.##...###.#.# ##.##.########.### ##.##..........### ...#############.. ####..###.....#### |
################## #.#SSSSSSSSSSSSSSS ###S############## #.#SSSSSS#####...# ########S#SSS#...# #SSSSS##S#S#S###.# #S###S##S#S#SSS#.# #SS##S##SSS###S#.# ##S##S########S### ##S##SSSSSSSSSS### SSS#############.. ####..###.....#### |
|
###.# ..#.# #.### #.### #.... ##### |
###.# SS#.# #S### #S### #SSSS ##### |
|
| Unsolved | Solved (65 and 8 steps) |
NOTE: The left table is actual program input, the right table is for visualization only!!!!
Sample Output:
65 steps
8 steps
The maximum number of columns in a maze will be 40. The maximum number of rows in a maze will be 50.
Return to the Top of Page, First Page, Novice Problem Set, or Veteran Problem Set.
Return to the Top of Page, First Page, or Veteran Problem Set.
Source Code for a Solution to this Problem
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE (! FALSE)
#define EOLN '\n'
#define DEBUG FALSE
#define MAXROWS 50
#define MAXCOLS 40
#define SPACE '.'
#define WALL '#'
#define BEEN 'S'
typedef char MazeType[MAXROWS][MAXCOLS];
MazeType maze;
int numrows;
int numcols;
int getline(char line[])
{ /* begin of FUNCTION getline */
int i;
char c;
i = 0;
c = getchar();
for (; ((c != EOF) && (c != EOLN)); ++i)
{ /* for */
line[i] = c;
c = getchar();
} /* for */
line[i] = '\0';
return (i > 0) ;
} /* end of FUNCTION getline */
int getmaze()
{ /* begin of FUNCTION getmaze */
int emptyline;
numrows = 0;
emptyline = (0 == getline(maze[numrows]));
numcols = strlen(maze[numrows]);
while (! emptyline)
{ /* while */
if (DEBUG) printf("%2d: |%s|\n",numrows,maze[numrows]);
numrows++;
emptyline = (0 == getline(maze[numrows]));
} /* while */
if (DEBUG) printf("Maze is %d x %d.\n",numrows, numcols);
return (numrows > 0);
} /* end of FUNCTION getmaze */
int openspace(int row, int col)
{ /* begin of FUNCTION openspace */
if ((row < 0) || (row > numrows) || (col < 0) || (col > numcols))
return (FALSE);
else /* valid place - now what is there */
return (maze[row][col] == SPACE);
} /* end of FUNCTION openspace */
void solvemaze()
{ /* begin of FUNCTION solvemaze */
int i;
int j;
int steps;
if (DEBUG) printf("Solving....\n");
for (i = 0; maze[i][0] != SPACE; i++);
steps = 0;
j = 0;
while (j < (numcols-1))
{ /* while */
maze[i][j] = BEEN;
steps++;
if (DEBUG) printf("Step: %d [%d,%d]\n",steps,i,j);
if (openspace(i+1,j)) /* check below */
i++;
else
if (openspace(i,j+1)) /* check right */
j++;
else
if (openspace(i-1,j)) /* check above */
i--;
else
if (openspace(i,j-1)) /* check left */
j--;
else
{
printf("Unsolveable maze - exiting....\n");
exit (-2);
}
} /* while */
maze[i][j] = BEEN;
steps++;
if (DEBUG) printf("Step: %d [%d,%d]\n",steps,i,j);
printf("%d steps\n",steps);
if (DEBUG) for (i=0; i < numrows; i++) printf("Solution: [%s]\n",maze[i]);
} /* end of FUNCTION solvemaze */
void main()
{
int mazetodo;
mazetodo = getmaze();
while (mazetodo)
{
solvemaze();
mazetodo = getmaze();
}
}
################## #.#............... ###.############## #.#......#####...# ########.#...#...# #.....##.#.#.###.# #.###.##.#.#...#.# #..##.##...###.#.# ##.##.########.### ##.##..........### ...#############.. ####..###.....#### ###.# ..#.# #.### #.### #.... #####
Return to the Top of Page, First Page, or Veteran Problem Set.
65 steps 8 steps
Return to the Top of Page, First Page, or Veteran Problem Set.
########################### ...############............ ##.###########..########### #..####.####...############ #.#####.####.############## #...###.####........####### ###.###.###########.####### ###..##...#######...###.### ####.############.######### ####.####...#####.######### ####.####.#####...#.#.#.### ####..###...###.###...#.### #####..####.###..##.#.#.### ######.##...####.########## ######..########.########## #######.###.#.##..######### #######..##.#.###.######### ########..#.#.##..######### ##.....##.#.#.#..########## ##.###..#.####..########### #...###.#.###..############ #########.....############# ###########################
Return to the Top of Page, First Page, or Veteran Problem Set.
87 steps
Return to the Top of Page, First Page, or Veteran Problem Set.
################# ################# ................. ################# ## .. ## . .. ## # . # ########## .........# ########.# #........# #.######## #......... ########## .........# ########.# #........# #.######## #.........
Return to the Top of Page, First Page, or Veteran Problem Set.
17 steps 2 steps 1 steps 2 steps 1 steps 28 steps 28 steps
Return to the Top of Page, First Page, or Veteran Problem Set.
Return to the LSU High School Programming Contest Homepage