Program | MOLECULE.C, MOLECULE.CPP, MOLECULE.PAS |
In this abstraction from a molecular engineering problem associated with developing a synthetic fuel, we are given four, equal length, molecular chains that are to form a super molecule. In the simplified two-dimensional model used here, the super molecule is formed as an interlocking rectangular arrangement of the four given molecular chain strands. The interlocking feature is the sharing of a common molecule between pairs of chains.
To illustrate, suppose we have the four, lengthtwelve, molecular chains:
OIMDIHEIAFNL
CHJDBJMHPJKD
LCBJOJGIEKBO
KAINLHLOLBEJ
These can be placed in the interlocking arrangements:
O |
L |
O |
C |
||||||
I |
C |
I |
H |
||||||
M |
B |
M |
J |
||||||
CHJ |
D |
BJMHP |
J |
KD |
D |
D |
|||
I |
O |
LCBJOJG |
I |
EK |
B |
O |
|||
H |
J |
or |
H |
J |
|||||
E |
G |
E |
M |
||||||
I |
I |
KA |
I |
NL |
H |
LOLBEJ |
|||
A |
E |
A |
P |
||||||
F |
K |
F |
J |
||||||
KAI |
N |
LHLOL |
B |
EJ |
N |
K |
|||
L |
O |
L |
L |
In this problem, we have some constraints on the arrangements being sought:
The first molecule designator within the first chain of a data set will be the letter “Q” to indicate the end of data.
Output
A line with a single integer is to be emitted for each input data set encountered.
This integer is the maximum area enclosed by any legitimate arrangement of the
four chains. Use the output value zero (0) to indicate that no legitimate super
molecule could be formed for a given data set. The first digit of an output
value should be the first character on a line.
Sample Input
CDBADCBBEFEF
DACCBADAFEAB
EFBDCAADBDCD
ABCDABCDABCD
DACCBADAFEAB
EFBDCAADBDCD
ABCDABCDABCD
CDBADCBBEFEF
ABABABABABAB
CDCDCDCDCDCD
EEEEEEEEEEEE
FFFFFFFFFFFF
ABAAAAAAAABA
CBCCCCCCCCBC
DBDDDDDDDDBD
EBEEEEEEEEBE
ABBBBBBBBBBA
ACCCCCCCCCCA
ADDDDDDDDDDA
AEEEEEEEEEEA
BBBABBBABBBB
CCACCCACCCCC
DDDDADDADDDD
EEAEEAEEEEEE
Q
Sample Output
48
48
0
64
0
6