首页 > ACM题库 > HDU-杭电 > hdu 4065 Catan待解决[解题报告]C++
2015
04-16

hdu 4065 Catan待解决[解题报告]C++

Catan

问题描述 :

The Settles of Catan is a multiplayer board game. It was one of the first German-style board games to achieve popularity outside of Europe.
The players in the game represent settlers establishing colonies on the island of Catan.Players build settlements, cities, and roads as they settle on the island. Certainly roads can connect the settlements and cities.Players build with resources such as brick, lumber, wool, grain, and ore.
Now look at the board below, do you see the hexagons tiles?
Carcassonne

There are six kinds of tiles. Five resources are mentioned above, and one is unproductive desert.
At the beginning of a game, the hexagons tiles will be randomly settled on the board, and each tile will be randomly assigned an integer ranging from 2 to 12. The desert will always be 7.
Every turn a player rolls two six-sided dices, determining which tiles produce resources.

To simplify the problem, we consider the construction phase at the beginning of the game, each player builds two settlements in this phase:
1.We have four players identified by 1,2,3,4.
2.On the first construction phase player 1,2,3,4 take turns to build a settlement separately.
On the second construction phase player 4,3,2,1 take turns to build a settlement separately.
3.Settlements can only be built on corners of the tiles, see the picture below, you are allowed to build settlements on the 54 corners signed with 0~53.

Carcassonne

4.Any two settlements couldn’t build adjacently, that means if a settlement have been built on the corner 19, then you couldn’t build another settlement on 9, 18 or 20.
5.The probability of the number rolled by two dices are different. For example, if we roll two dices 36 times, the expectation to get 6 or 8 is 5 times, while the expectation to get 2 or 12 is 1.
For example, look the picture, if I build two settlement at 32 and 20,then the expectation is 4(9) + 4(9) + 3(4) + 5(6) + 2(11) + 4(9) = 22.
6.To get better development,you should try you best to get all five kinds of resources.
7.Other players are greedy, when they turn to build settlement, they will choose the corners with highest expectation (if more than one such corners, they will choose the one with minimum sign).

Now as player 1, you should choose the best strategy for building settlement to make the expectation as high as possible.(the expectation calculated by roll two dices 36 times)

输入:

The first line is a number T(1<=T<=50), represents the number of case. The next T blocks follow each indicates a case.
Five lines follow, indicate the situation.
‘B’ indicate the Brick.
‘W’ indicate the Wool.
‘L’ indicate the Lumber.
‘G’ indicate the Grain.
‘O’ indicate the Ore.
‘D’ indicate the Desert.
Then five lines follow.
Each number indication the number sign of this tile.
There is an empty line between cases.

输出:

The first line is a number T(1<=T<=50), represents the number of case. The next T blocks follow each indicates a case.
Five lines follow, indicate the situation.
‘B’ indicate the Brick.
‘W’ indicate the Wool.
‘L’ indicate the Lumber.
‘G’ indicate the Grain.
‘O’ indicate the Ore.
‘D’ indicate the Desert.
Then five lines follow.
Each number indication the number sign of this tile.
There is an empty line between cases.

样例输入:

2
  O B B
 G W G W
O L L G G
 L D O B
  B O W
  8 10 9
 3 4 5 12
6 9 11 6 11
 2 7 3  4
  5 10 8

  B W L 
 D W L B 
L D G B D 
 L O D W 
  D G W 
  8 3 8 
 7 2 8 6 
9 7 9 8 7 
 9 3 7 6 
  7 3 8 

样例输出:

Case 1: 19
Case 2: -1

Hint
For case1,I will choose 18 and 45 to build settlement