TopCoder SRM 558 - 1000: SurroundingGame

Problem Statement

题目简述

以网格图的形式给出一个无根树，

以及树的点集的一个子集 C。

现从 C 的所有大小为 K 的子集中等概率选取一个子集 S，

记 length 为树中经过所有 S 中的点的最短路径长度

（路径长度定义为经过的边数，可以重复经过同一条边，此时长度需要被计算多次）。

给定无根树、点集 C 以及整数 K，求 length 的期望值。

树的节点数不超过 50*50，c<=300，2<=K<=|C|。

Mrs. Jeipouju is planning to practice orienteering. The area where she'll practice is a rectangular field divided into unit squares. You are given its description as a String[] field. Each character in field is '.' (a period), '*' (an asterisk), or '#' (a number sign). Each '.' represents a passable square without a checkpoint, each '*' represents a passable square with a checkpoint, and each '#' represents an impassable obstacle. It is guaranteed that all passable squares (i.e., all '.'s and '*'s) form a 4-connected tree (see notes for formal definition). The number of checkpoints is at most 300.

In order to practice, Mrs. Jeipouju chooses K of the checkpoints uniformly at random. Afterwards, she will find the shortest sequence of squares that passes through all chosen checkpoints. The sequence can start at any square, end at any square (possibly other than the starting one), and visit each square any number of times. Each pair of consecutive squares in the sequence must have a common side. The length of the sequence is the number of moves Mrs. Jeipouju will have to make. (So, for example, a sequence that consists of 7 squares has length 6.)

You are given the String[] field and the int K. Return the expected length of Mrs. Jeipouju's sequence.

Definition

Class Orienteering
Method expectedLength
Parameters vector<string> , int
Returns double
Method signature double expectedLength(vector<string> field, int K)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Notes

A set S of squares is said to form a 4-connected tree if for any two squares A and B from S, there exists exactly one way to walk from A to B while visiting only the squares from S and not visiting the same square more than once. From a given square, it is possible to walk into any square that shares a common side with it.

Constraints

field will contain between 1 and 50 elements, inclusive.
Each element of field will contain between 1 and 50 characters, inclusive.
Each element of field will contain the same number of characters.
Each character in field will be '*', '.', or '#'.
'*' and '.' form a 4-connected tree.
K will be between 2 and 300, inclusive.
field will contain between K and 300 '*', inclusive.

Test cases

input
- field {"*#..#",
  ".#*#.",
  "*...*"}
- K 2
output
Returns 3.8333333333333353
note
Let (i,j) be the square represented by the j-th character of the i-th element of field (both numbers are 0-based).
- If she chooses (0,0) and (1,2), one of the optimal sequences is (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (1,2).
- If she chooses (0,0) and (2,0), one of the optimal sequences is (0,0) -> (1,0) -> (2,0).
- If she chooses (0,0) and (2,4), one of the optimal sequences is (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (2,3) -> (2,4).
- If she chooses (1,2) and (2,0), one of the optimal sequences is (1,2) -> (2,2) -> (2,1) -> (2,0).
- If she chooses (1,2) and (2,4), one of the optimal sequences is (1,2) -> (2,2) -> (2,3) -> (2,4).
- If she chooses (2,0) and (2,4), one of the optimal sequences is (2,0) -> (2,1) -> (2,2) -> (2,3) -> (2,4).
So the expected length of her sequences is (5 + 2 + 6 + 3 + 3 + 4) / 6 = 23 / 6.
input
- field {"*#..#",
  ".#*#.",
  "*...*"}
- K 4
output
Returns 8.0

note

Mrs. Jeipouju chooses all four checkpoints. One of the shortest sequences is (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (1,2) -> (2,2) -> (2,3) -> (2,4).
input
- field {"#.#**",
  "....#",
  "#*#**",
  "**#*#",
  "#..##",
  "*#..#",
  ".#.#.",
  "....*"}
- K 3
output
Returns 10.825000000000024
input
- field {"###################",
  "#*###############*#",
  "#.....#######.....#",
  "#*###*.#.*.#.*###*#",
  "#*####*.*#*.*####*#",
  "#*#####*###*#####*#",
  "###################"}
- K 9
output
Returns 30.272233648704244
input
- field {"**##*.**#..#.*...*#...*#..#.##..#..#.#*...#.##*##.",
  ".#..###..#..#.#.##..#.#.*#.*..#..#.#*..##.#*...*..",
  "..#.....###.#*.##..#.#.#*..#.#..#....#..#...#*####",
  ".#.##*#.*#..#*#*.#.#...*.#.*#.#.##.#*.##.#.#..*...",
  "..*.*#*.###.#..#.#..##.##.*#..#.....#.....#..#.#.#",
  ".#.##.#..##..*#..#.#...#*##*#*..#.#.#.#.##.##.#.#*",
  "..##....#..#.#*#...*.##...#.#.####...#.#*.....#...",
  ".#.*#.##.*#*.#*.#.#.#..#.#..#.#*#.###..##.##.#.##*",
  ".*.#*..*.#.#...#.*##.#.**.#.*...**..*#..#.#.#*.#..",
  ".#*.#*##....##.#.#*..*.###.#.##.##.#.#.#....#.#*.#",
  "*.#..#*#.#*#*....#.#.#..*#**...##.#.#.**#*##.*.#..",
  ".#*.##..##..##.#.#..#.#.###.###...#...#*#..##*#.#.",
  "#..#*.#..*.###..#.#...#.###.#.#*#.#.#**##.#...*.#*",
  "..#..#.#.##.#..#.**.##*#.#**.**..#.#..#...#.##*#..",
  ".#*#.#.*..#.*#...#.#...#...#.##.#..*#*.##*....###.",
  ".*.#.#.#.#*#..*##.**.##*##..#.*#.#*###..*.#.##.#..",
  ".#......#...#.#.*#.#.#..#..#.#*#....#*.#*#.*#..*.#",
  "#..####..#*#...#*.#..#.###...#.#.#.###*#..##*##.#.",
  ".#.*..#.#...#.#..#.##...#..#.#.#.#.###..##..*.*.*.",
  ".#.#.#.#..##.*..#.*.#.##.#..##*...#.#..#.#.##.#.##",
  ".#..#*.#.#..#.##..##..#.*..#.*#.#...##....#...###.",
  ".#.#.#.#*.#.#..#.#..#..#.#.*#...#.##...#.##.##.*..",
  ".#...#.#.##.#.#..*#.*#..###..#.#.#*###.##...#*.##.",
  ".#.##.*.......*.#.*#.#.#*###..*...*..#.*.##.#.#..#",
  "...###*####*#.#..##*...#..#..##.#.#.#..##*#*.*.*#.",
  "#.#.#....*#..#.#.#.#.##..#*.#...#..#.#*#...#.##.*.",
  "..*.#*##.#.#*#.###...#..##.#.#.#*###*#.*#.#.*###.#",
  "##*##..##...#.....##.#.#.**#..#*.....##.#..#*.#.*.",
  ".....#.*.##..##.##*.*#...#.#.#.##.#*#.**..#..#.#.#",
  "##.#.#*##.#.#.*.*.#.#*#.#.#....*...#*##*##.#....#.",
  "*.**#**....*..##.#*.*.**..##.###.##.....##...##.**",
  "#.####.##*#*##..#.*#*#.##*...#.##..#.##....#*..##.",
  "....#...##.#...#*.#..##.##.#*..*.#....##.#.*##...#",
  "#.#..*##*..#.#..#..#..#*....#.##..##.#*##.##.*##..",
  "..#.#*.*.##.#.#*#.#*##.###.##...#............#*.#.",
  "#.#.##.#....*....*..##..*#.#.#.###.#.#.#.###..#..#",
  ".#**..#*#.#*#*#.#.#...*##....##.#*..#..#*..*#..#..",
  "...#*#.....#..#.#..#*#.*##.#..#.#.##..#.*#*#.#...#",
  ".#*.###.#.#.#.#.*#*##.##..#.#*..#...#.#.#..#*.*#..",
  "#*.#.#.#..#..#..#....*#.*##..##.#.#..#...##.#.#..#",
  "*.#..#..#...#..##.#*#..#.#*#.#.#.###..#.#*...#.#..",
  "#...#.#...#.#.#..#.*.#*.....**.*..#*##.#*.##....##",
  "#*#....#*#..#.*.###*#..#*##.##.#.#...#.*.##.##.##.",
  "..##*##*..#*#.#..#*.*##*.##.#...#.#.#.#.#..*#.##..",
  "#...#*##.#*#**.##.*#.*.##..*.#*#**....#**##...*.*#",
  "*#.##......*#.##.#.#.##**.#.#.#.#.#.##..#...#*#*#*",
  "*....##.#.#..#.....#..##.#....*....#.#.##.#.#.##**",
  "#.##*#...#..#.#.##..#..##.##.##.##........##.#*#.#",
  "..#...#.#*#*..*#..*#.*#.#......##.#.#.#*#..#..****",
  ".###.#..#...#.#..#..#.#...#.#.#...**.#..*#*.*##*#."}
- K 150
output
Returns 1309.4951033725558

back to the menu