Write a C++ Program for Splitting the Choco Bars Problem

By | February 23, 2017

C++ Program for Splitting the Choco Bars


 

Dholu and Bholu are given chocolate bars which are rectangular shaped.Each chocolate is given a label A, B and C. The chocolate is to be splitted into exactly two pieces in a manner such that:

The piece that Dholu has can not contain any chocolate with name B.In the same way Bholu’s piece can not contain any chocolate labeled A. The chocolate C can be used by both of them.

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 that exists between the number of chocolates in pieces should not be more than K.

Now the chocolates have been divided into two pieces.Now in any piece there should not be 4 adjacent chocolates that form a square. Hence,there should not be any part of chocolate in the given pattern:

XX XX


Explanation


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

CC

CC

Sample Output

12

Explanation

Note: In the explanation A and B are used to represent, which parts belong to Dholu and Bholu respectively. There are 24 = 16 possible separations. The 4 invalid are:

AA

AA

BB

BB

BA

AB

AB

BA

Some of the valid ones are:

AB

AB

AA

BB

BB

AA

BA

BA

Explanation

Note: In the explanation T and D are used to represent, which parts belong to Tom and Derpina respectively. There are 24 = 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

Time Limit:3.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

SOURCE CODE : :

 

OUTPUT : :

Leave a Reply

Your email address will not be published. Required fields are marked *