Counting Holes on a Floating Bread

Problem Statement

You are an ant stranded on a floating piece of bread. This bread can be regarded as a 3D solid formed by several unit cubes. The cubes are placed in a single layer (i.e. at most one cube high) and the configuration is connected. Thus the bread is represented by a grid where a cell with a cube is marked by '1' and an empty cell by '0'.

The external surface of this bread is made up of all faces that are not shared by two adjacent cubes. You start on one of these faces (always on the top face of a cube) at a given position and orientation. You are then given a sequence of q operations. In each operation you can do one of the following:

• K: Move forward one unit (that is, across the current face through its edge to the adjacent face on the same cube or a neighbouring cube, with wrapping over the edge if necessary).
• L: Turn left 90° relative to your current facing.
• D: Turn right 90° relative to your current facing.
• X: Toggle a mark on the current face (if there is a mark, remove it; if not, add one).

Note: The movement simulation is only for flavor – regardless of your journey or the marking actions you perform, the underlying bread (i.e. the arrangement of cubes) does not change.

Holes

We define a hole in the bread as a connected region of empty space (0's in the grid) that is completely enclosed by the cubes. In other words, if you perform a flood fill from the boundary of the grid, the remaining connected regions of 0's (which do not touch the boundary) are holes. Your task is to compute the number of holes in the bread.

Input Format

The input consists of the following parts in order:

1. A line containing two integers R and C (the number of rows and columns of the grid).
2. R lines, each consisting of a string of C characters. Each character is either 1 (representing a cube) or 0 (representing empty space).
3. A line containing two integers r0 and c0 (the starting row and column, 1-indexed) and a character d (the initial facing direction, one of N, E, S, W). (This information is provided for the narrative and does not affect the final answer.)
4. A line containing an integer q – the number of operations.
5. A line containing a string of q characters. Each character is one of K, L, D, X (the operations to be performed). (Again, these operations do not alter the bread.)

Output Format

Output a single integer – the number of holes in the bread.

inputFormat

The input begins with two integers R and C on one line. Then follow R lines each containing a string of C characters ('1' or '0'). Next is a line with two integers r0 and c0 and a character d (N, E, S, or W), representing the starting position and initial direction. After that, an integer q is given, followed by a line with a string of q characters (each one from {K, L, D, X}).

Note: The starting position, direction, and the operations are only part of the story and do not affect the structure of the bread. The answer depends solely on the grid configuration.

outputFormat

Output a single integer – the number of enclosed holes in the bread (i.e. the number of connected regions of '0's that do not touch the boundary of the grid).

sample

5 5
00000
01110
01010
01110
00000
3 3 N
5
KXLXD

1