首页 > ACM题库 > HDU-杭电 > hdu 4402 Magic Board待解决[解题报告]C++
2015
05-24

hdu 4402 Magic Board待解决[解题报告]C++

Magic Board

问题描述 :

Sths is a happy boy~

Sths has got a Magic Board for his birthday gift! A Magic board is an N*M sized grids which were painted by black and white. According to the parity of N and M, the Magic Board would be a little different, but it can be guaranteed that any two adjacent grids are painted by different colors, and the amount of black grid is not less than white ones.

Battery

The Magic Board is called MAGIC because it is formed by a Chain. A Chain is a set of grids in which a grid has at most 2 adjacent grids and there are only 2 grids which has only 1 adjacent grid. Those two special grids are called the endpoints of the Chain.

The joint between two adjacent grids is very flexible. It can be rotate by any angle. Here’s an example of transforming a Chain into a Magic Board

Battery

The Chain was connected by a Magic String. The existence of Magic String relies on the power of fengshui. But recently the fengshui in Beijing was ruined because there is a university installing air-conditionor (which also cause the HUGE RAIN in Beijing).So the Magic String disappears, and the Magic Board is totally fell apart.

Sths feels upset, because he really likes the Magic Board (since it can form a lot of things). So he is thinking about how to reconstruct it. The only thing Sths has got now is the separated grids. But surprisingly, Sths finds out that there are differences between these grids.

1. There are black grids and white grids.
2. There are three different grids in the same color because the Magic String goes through it in 3 different ways shown below:

Battery

So there are 6 different kinds of grids. Now Sths has counted the amount of each kind of grids, he wants to know: by using the grids in his hand, how many kinds of legal Chains (which can form an N*M sized Magic Board) can be constructed.
  
We shall say two Chains is the same if and only if the standard expression of these two Chains is the same.

The standard expression is a set of numbers which decided by following method:

1. Starting from one of a Chain’s endpoint.
2. Write down the color of the grids (1 for black and 0 for white) before direction changing.
3. Write down 2 then change direction and repeat Step 2 until reaching another endpoint of the Chain.
4. Choose the expression which lexicographical lower between the two expressions just generated since there are two endpoints.

For example, the standard expression of the example of “N=M=3” is “10120120120212” (another expression is “10212012012012”, which is lexicographical greater than standard expression). And the standard expression of the example of “N=M=4” is “01012010210120120120212”.

输入:

There are Multiple Test Cases
For each case, there will be six integer numbers in one line, N, M, BO, BA, WO, and WA, indicating the number of rows and columns, the amount of “Black and Opposite” grids, the amount of “Black and Adjacent” grids, the amount of “White and Opposite” grids, the amount of “White and Adjacent” grids.

2<=N*M<=30

The input end with a line of 0 0 0 0 0 0.

输出:

There are Multiple Test Cases
For each case, there will be six integer numbers in one line, N, M, BO, BA, WO, and WA, indicating the number of rows and columns, the amount of “Black and Opposite” grids, the amount of “Black and Adjacent” grids, the amount of “White and Opposite” grids, the amount of “White and Adjacent” grids.

2<=N*M<=30

The input end with a line of 0 0 0 0 0 0.

样例输入:

3 3 1 2 2 2
3 3 0 3 3 1
5 5 5 6 5 7
0 0 0 0 0 0

样例输出:

1
1
4