Description
A common approach to navigating garden mazes is to, upon entry to the maze, to place one's hand upon the wall to 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.
Write a program to read in a description of a maze marked with a goal location and one or more entrances, and to 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 location or reaches any position with an unimpeded view to the goal along a vertical or horizontal line.
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.
Output
For each maze, print a single line of output of the form
The goal would be found from ? out of ? entrances.
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.
Sample Input
31 15
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X X
X X
X X
X XXXX XXXXX X
X X X X
X X G X X
X X X X
X X X X
X XXXXXXXXXX X
X X
X X
X XXXXXXXXXXXXX
X X
XXXXXXEXXXXXXXXXXXXXXXEXXXXXXXX
0 0
Sample Output
The goal would be found from 1 out of 2 entrances.
http://poj.org/problem?id=2816
