首页 > ACM题库 > HDU-杭电 > hdu 2358 Another Version of the Truth待解决[解题报告]C++
2014
01-05

hdu 2358 Another Version of the Truth待解决[解题报告]C++

Another Version of the Truth

问题描述 :

Influence is a board game; while it can be played on almost any layout, an interesting layout is a hexagonal NxN grid, such that the layout resembles
a rhombus.

An example 9×9 board is as follows:


1 2 3 4 5 6 7 8 9
\ \ \ \ \ \ \ \ \
* * * * * * * * * ― A
* * * * * * * * * ― B
* * * * * * * * * ― C
* * * * * * * * * ― D
* * * * * * * * * ― E
* * * * * * * * * ― F
* * * * * * * * * ― G
* * * * * * * * * ― H
* * * * * * * * * ― I

On the above grid, F5 is adjacent to F4, F6, E5, E6, G4, and G5. (These coordinates are not used in the problem, but are useful for understanding the
underlying adjacencies.)

The rules of Influence are simple; the pertinent details are as follows:

Players take turns placing Manipulators on the board. Manipulators occupy a single location, and there may be at most one Manipulator at a
location. If there is no empty location on the board to place a piece, the player must pass their turn.
Each player has a certain amount of Influence. A player has a single point of Influence for every location on the board that is strictly closer to
one of their Manipulators than a Manipulator of any other player. This is not "straight-line" distance, but the number of cells in a minimal path
to a Manipulator. On the above grid, the cell F5 is 2 steps away from G6, 1 step away from G5, and 0 steps away from itself.
The player with the most Influence at the end of the game wins.

In the sample input below, the first player (represented by "!" marks) has only two Influence, that provided by the locations that his Manipulators are
on; the second player (represented by "@" signs) has ten Influence, and the third player (represented by "#" marks) has four Influence. There are
nine locations that provide Influence to no player, as they are equally distant from two or more of the players.

Given a particular board layout, answer this question: what would the resulting Influence be for each player’s optimal move if they were making the
last move in the game?

Moves are to be considered independently; that is, the maximum score for the second player should be calculated based on the original board layout,
not the one after the first player’s best move.

输入:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A line containing a single integer P (2 ≤ P ≤ 4) indicating the number of players in the game;
A line containing a single integer D (1 ≤ D ≤ 26) indicating the board’s dimension (9 would represent the 9×9 board above); and
A series of D lines, each representing a row on the board from top to bottom. Each location on the row is represented by one of the following
characters, separated by spaces:
. ― An empty location;
! ― A piece for the first player;
@ ― A piece for the second player;
# ― A piece for the third player (if playing); or
$ ― A piece for the fourth player (if playing).
Note that there may be extra whitespace on these lines (and only these lines). This is to make the input resemble the layout shown above.

输出:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A line containing a single integer P (2 ≤ P ≤ 4) indicating the number of players in the game;
A line containing a single integer D (1 ≤ D ≤ 26) indicating the board’s dimension (9 would represent the 9×9 board above); and
A series of D lines, each representing a row on the board from top to bottom. Each location on the row is represented by one of the following
characters, separated by spaces:
. ― An empty location;
! ― A piece for the first player;
@ ― A piece for the second player;
# ― A piece for the third player (if playing); or
$ ― A piece for the fourth player (if playing).
Note that there may be extra whitespace on these lines (and only these lines). This is to make the input resemble the layout shown above.

样例输入:

1
3
5
! . . # .
 . @ . . !
  . . . . #
   . . @ . .
    . . . . .

样例输出:

DATA SET #1
5
13
7


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧