[email protected] High School Programming Competition 2019

Tree Skiing

Photo by Ptahhotep. Retrieved from Wikimedia.

After a long drive, you and your friend have arrived at the ski slope. There is a ton of new snow, the sun is shining, and you are both feeling adventurous! When you get off the lift, you see that a new run has been opened through the trees. Strangely, the trees in this forest have grown in a perfectly compass-aligned grid.

Your friend heads off down the slope weaving her way around the trees. Eventually, she stops in a clearing to make a snow angel. You want to join her to make a snow angel as well, but you do not want to waste the opportunity to ski on the fresh powder. You go looking for a new path through the forest.

You can’t ski straight down the mountain to your friend
because there are trees in the way. At each clearing you have
an option to head directly north or directly west out of the
clearing. You don’t want to climb back uphill to the south or
east. Once you pass the clearing and enter the next, you have
to make the same decision again and again. How many different
ways can you ski through the trees until you reach the clearing
where your friend is playing in the snow, without skiing on
*exactly* the same path as she skied and without hitting
a tree on your way down?

The first line of input contains an integer $1 \leq n \leq 20$. The second line of
input contains $n$
characters separated by spaces which specify, in order, the
directions your friend went at each clearing. The characters
are limited to `N` for north and
`W` for west.

The output should contain a single integer: the number of
other possible paths you could take to meet up with your
friend. For example, in Sample Input $1$ there are $3$ paths total to the clearing where
your friend is making snow angels. Your friend went north,
north again, then west. You can go either north, west, then
north *or* west, north, then north. So there are
$2$ new ways for you to
get to the clearing. Note that the output could be $0$ if, for example, your friend took
the only path to the clearing.

Sample Input 1 | Sample Output 1 |
---|---|

3 N N W |
2 |

Sample Input 2 | Sample Output 2 |
---|---|

4 N W N W |
5 |