We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- Practice
- Algorithms
- Dynamic Programming
- Separate the chocolate

# Separate the chocolate

# Separate the chocolate

Chinese Version

Russian Version

Tom and Derpina have a rectangular shaped chocolate bar with chocolates labeled T, D and U. They want to split the bar into exactly two pieces such that:

- Tom's piece can not contain any chocolate labeled D and similarly, Derpina's piece can not contain any chocolate labeled T and U can be used by either of the two.
- All chocolates in each piece must be connected (two chocolates are connected if they share an edge), i.e. the chocolates should form one connected component
- The absolute difference between the number of chocolates in pieces should be at most K
- After dividing it into exactly two pieces, in any piece, there should not be 4 adjacent chocolates that form a square, i.e. there should not be a fragment like this:

XX

XX

**Input Format**

The first line of the input contains 3 integers M, N and K separated by a single space.

M lines follow, each of which contains N characters.
Each character is 'T','D' or 'U'.

**Constraints**

0≤ M, N ≤8

0≤ K ≤ M * N

**Output Format**

A single line containing the number of ways to divide the chocolate bar.

**Sample Input**

```
2 2 4
UU
UU
```

**Sample Output**

```
12
```

**Explanation**

**Note:** In the explanation T and D are used to represent, which parts belong to Tom and Derpina respectively.
There are 2^{4} = 16 possible separations. The 4 invalid are:

```
TT
TT
DD
DD
DT
TD
TD
DT
```

Some of the valid ones are:

```
TD
TD
TT
DD
DD
TT
DT
DT
```