程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 編程解疑 >> lines-Right-Hand Rule

lines-Right-Hand Rule

編輯:編程解疑
Right-Hand Rule

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved