Counting Possible Boat Positions

In the game "Sailing", two teams compete with each team having a captain and a scout. At the beginning of each round, each captain selects a starting point on a map represented by a binary matrix where 0 indicates water (passable) and 1 indicates an obstacle (impassable). The captain must choose a starting position that is 0. Then, in each round, the captain commands the boat to move exactly one unit in one of the four directions: up, down, left, or right. The boat can only move into a cell that is within the boundaries of the map and is 0. After making the move, the captain announces the direction he has moved.

Jasmine, a scout, has recorded the enemy boat's sequence of movement directions but does not know its initial starting position. Initially, the enemy boat could have started at any cell that is 0. For each possible starting position, if following the sequence of moves results in a valid path (i.e. every move is legal), then that final position is a candidate. Your task is to determine the number of distinct final positions that the enemy boat could be in after executing the recorded moves.

The moves are represented by the characters:

• U for Up, which means moving from \( (i,j) \) to \( (i-1,j) \).
• D for Down, moving to \( (i+1,j) \).
• L for Left, moving to \( (i,j-1) \).
• R for Right, moving to \( (i,j+1) \).

A move is valid if and only if the destination cell exists within the bounds of the map and is 0. If at any move the boat would either leave the map or enter an obstacle (1), then that starting position is discarded.

Your goal is to count the number of distinct final positions achievable by following the given move sequence from some valid starting position.

Formally, if we denote the move direction vectors as:

[ \text{U} = (-1, 0),\quad \text{D} = (1, 0),\quad \text{L} = (0, -1),\quad \text{R} = (0, 1), ]

and if \(S\) is the set of all starting positions \((i, j)\) in the grid with value 0, then for each starting position \((i, j)\) we simulate the move sequence. If the boat remains on valid water cells throughout, let \(f(i,j)\) be the resulting final cell. The answer is the number of distinct cells among \(\{f(i,j) : (i,j) \in S\}\) that are reached from at least one starting position without any invalid move.

inputFormat

The first line contains two integers \(R\) and \(C\) (the number of rows and columns of the map).

The next \(R\) lines each contain a string of length \(C\) consisting of the characters 0 and 1 representing the map.

The last line contains a string consisting of the characters U, D, L, and R which denotes the recorded move sequence. The move sequence may be empty, in which case no moves are made.

All tokens are separated by whitespace or newlines.

outputFormat

Output a single integer which is the number of distinct final positions that can be reached by following the given move sequence from some valid starting position.

sample

3 3
000
010
000
R

4