## Baltic OI '19 P2 - Nautilus

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
##### Baltic Olympiad in Informatics: 2019 Day 1, Problem 2

Nautilus is a secret submarine, sailing around the ocean and trying to remain hidden. The ocean is modelled as an grid of cells, where # represents islands and . represents water. For example:

...##....
..#.##..#
..#....##
.##...#..
....#....

Every minute, Nautilus emits a radio signal that can reveal the direction the submarine is about to take. The direction is always one of the following: North (N), East (E), South (S), West (W), as shown on the figure above right.

Vytautas has constructed a radar that intercepts the periodic submarine signals. Over the last minutes, the radar has collected radio signals, represented as a sequence of characters, for example WS?EE??. Some of the signals could not be decoded, these are marked as ?.

Vytautas does not know the initial submarine location, but wants to use the ocean map in order to identify its current location. Given that Nautilus always stays in water cells on the map, help Vytautas calculate the number of distinct cells where Nautilus may be located at currently.

#### Input Specification

The first line of the input contains three integers , , . The next lines form an grid of characters # and . representing the ocean map. The last line of the input describes the signals intercepted by Vytautas — a string of characters, all belonging to the set {N,E,S,W,?}.

#### Output Specification

Output a single integer: the number of possible distinct current positions of Nautilus.

#### Sample Input

5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??

#### Sample Output

22

1. ( points) ; there are no ? symbols.