Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Task: Fence Factory
发信站: 哈工大紫丁香 (2002年03月29日13:53:09 星期五), 站内信件

Task: Fence Factory
Figure 1: Four fences and some of their letter strings (joints not to scale)

A factory makes a modular fence system. The fence sections are one unit long
 and may be linked together using a separate joint. A joint always links two
 sections. Unfortunately, the machine that makes straight joints has broken 
down. The machine for right-angled (90°) joints still works, and can make l
eft-handed and right-handed joints.
The factory's computer scientist is asked to work out what shapes can be mad
e with right-angled joints only. The computer scientist decides to describe 
a fence by a string of letters. Each letter tells whether the next section i
s joined to the left (L) or the right (R).
The string LRL describes a zigzag, consisting of 4 sections (Figure 1a; the 
joint `cutoff' is greatly exaggerated). The string LLLL describes a closed s
quare (Figure 1b). Some strings describe impossible shapes that intersect th
emselves, e.g. RLLLL.
From now on we consider only strings describing possible shapes that are clo
sed.
A closed shape can be encoded in several ways, depending on where you start 
and the direction you go. For example, the strings LLLRLLLR and RLRRRLRR des
cribe the same closed shape (Figure 1c).
Write a program that inputs a string describing a closed shape, and answers 
the following questions for this shape:
A
How large is the enclosed area, in square units? Space that can be reached f
rom outside by squeezing in between two joints is not considered enclosed (s
ee Figure 1d: the enclosed area is shaded).
B
Which strings describe this shape?
Input and Output Data
The input file INPUT.TXT consists of one line containing a single string and
 nothing else. A string consists of at least 4 and at most 50 letters.
The output file OUTPUT.TXT should consist of at least two lines. On the firs
t line is a single positive integer: the area enclosed by the shape (Subtask
 A). The next lines each contain a string describing the shape (Subtask B). 
These strings may be given in any order, but they must all be different.
Figure 2 gives example input and output files corresponding to Figure 1c.
____________   _____________
|INPUT.TXT |   |OUTPUT.TXT |
|__________|   |___________|
|LLLRLLLR  |   |2          |
|__________|   |LLLRLLLR   |
               |LLRLLLRL   |
               |LRLLLRLL   |
               |RLLLRLLL   |
               |RRRLRRRL   |
               |RRLRRRLR   |
               |RLRRRLRR   |
               |LRRRLRRR   |
               |___________|
Figure 2: Example input and output

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]