Right-Hand Rule A common approach to navigating garden mazes is, upon entry to t

Question

Right-Hand Rule

A common approach to navigating garden mazes is, upon entry to the maze, to place one’s hand upon the wall to the right of the entrance, and then to walk forward, keeping that right hand in contact with a wall at all times.

It’s well known that this technique allows one to pass through one-entrance, one-exit mazes, but it does not always suffice with mazes where one is supposed to reach some goal location or locations in the interior of the maze.

This program should read in a description of a maze marked with a goal location and one or more entrances, and should determine whether the goal can be found by applying the right-hand rule until the goal is found or until the rule causes you to pass outside the maze through one of the entrances.

We assume that people walking through the maze will look around as they do so. Consequently, a goal is considered to have been “found” if the person steps directly onto that goal location or reaches any position with an unimpeded view to the goal along a vertical or horizontal line.

2.1 Input

Input consists of one or more mazes. Each maze begins with a line containing two integers, w and h, denoting the width and the height of the maze. End of input is indicated when either of these values is less than 3.

This is followed by h lines of input. In each of these lines, only the first w characters are significant. If the input line contains fewer than w characters, you should treat the missing characters as ‘X’.

The interpretation of the characters in these lines is as follows:

‘ ’ denotes an open space

‘G’ is an open space representing a goal location - there will be exactly one of these in any maze.

‘X’ denotes a wall

‘E’ is an open space representing an entrance. All entrances will occur on the outer perimeter (as defined by the w and h values) of the maze and no two entrances will be adjacent.

All mazes will be completely enclosed by a combination of ‘X’ and ‘E’ characters.

2.2 Output

For each maze, print a single line of output of the form

replacing the first ‘?’ by the number of entrances from which the right-hand-rule allows one to find the goal and the second ‘?’ by the total number of entrances.

2.3 Example

2.3.1 Input:

2.3.2 Output

test2.in: Your simplified test test

righthand.cpp: Your version of the program with your debugging output included and active.

debugLog.txt: Your log of the debugging process, including your final diagnosis

RIGHTHAND.CPP

TEST1.GOLD

TEST1.IN

Explanation / Answer

RIGHTHAND.CPP

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.