## RTE '16 S2 - Fire Evacuation Plan

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Python 2 1.4s
Python 3 1.4s
Memory limit: 64M
Python 2 64M
Python 3 64M

Author:
Problem type

At RHHS, the school is on fire every other day, because safety is our number one priority. After administration has decided enough was enough, they decided to place detailed evacuation plans in each and every classroom to ensure everyone's safety during fire evacuations.

An evacuation plan consists of a list of movements in cardinal directions (North, South, East, West), which detail the exact movements a student must make in order to make it to safety.

One such evacuation plan may be NNWS, which describes an evacuation plan where the student must move one meter north, one meter north, one meter west, then one meter south in order to reach safety.

However, administration has decided that these evacuation plans were too easy to follow, and did not foster the academic atmosphere RHHS is so famously known for having. As a result, administration decided to encode the evacuation plans with a different encoding for each room.

With this encoding, each cardinal direction is replaced with a string of letters, and the final evacuation plan is the concatenation of this string of letters.

For example, the following mapping represents a possible encoding:

N → AA
S → A
E → B
W → AB

With this encoding, our original evacuation plan of NNWS becomes AAAAABA.

A side effect of this encoding is that it may represent multiple possible original evacuation plans. With the above encoding, AAAAABA could not only represent NNWS, but also SSSSSES.

Given an encoding and an evacuation plan, determine the number of possible distinct destinations the evacuation plan could lead to.

#### Input Specification

The first four lines will contain the encoding for North, South, East, and West respectively. Each encoding will not exceed characters.

The next line will contain an evacuation plan encoded with the given encoding, of length .

For test cases worth 20 of 100 points, .

#### Output Specification

Output a single integer representing the number of possible distinct destinations the evacuation plan may lead to.

#### Sample Input

AA
A
B
AB
AAAAABA

#### Sample Output

6

#### Explanation of Sample Output

The possible original evacuation plans the encoded plan may represent are as follows:

NNSES
NNWS
NSNES
NSSSES
NSSWS
SNNES
SNSSES
SNSWS
SSNSES
SSNWS
SSSNES
SSSSSES
SSSSWS

However, many of them represent the same destination (for example, NNSES and NSNES are both syntactically identical to E). 6 of these plans lead to a distinct location.