1999 LSU Computer Science High School Programming Contest
Veteran Problem 7
Amazing!

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.

Clarifications:






Return to the Top of Page, First Page, or Veteran Problem Set.


The statements and opinions included in these pages are those of the LSU High School Programming Contest Staff only. Any statements and opinions included in these pages are not those of Louisiana State University or the LSU Board of Supervisors.
© 1999 LSU High School Programming Contest

Return to the LSU High School Programming Contest Homepage