Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Right-Hand Rule
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 502Accepted: 139

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.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator