f****e
发帖数: 923 | 1 An orienteering map is to be given in the following format.
########
#@....G#
##.##@##
#[email protected]#
#@.....#
########
Calculate the minimum distance from the start(S) to the goal(G) with passing
all the checkpoints(@). Specification ‘.’ means an opened-block that
players can pass. ‘#’ means a closed-block that players cannot pass. It is
allowed to move only by one step vertically or horizontally.
1 <= w <= 100, 1 <= h <= 100
The maximum number of checkpoints is 18.
Return -1 if given arguments do not satisfy specifications, or players
cannot arrive at the goal from the start by passing all the checkpoints.
The input is to be given in the following format, from the standard input.
W H
Row1
Row2
...
RowH
The first row is to describe the width and the height of the orienteering
map, sectioned by a space. Output Output into the standard output, and put a
return.
And later I also have to print the path. |
z*********n
发帖数: 1451 | 2 这就是TSP变种吧。直接暴力搜+剪枝make sense吧？ |
r*****s
发帖数: 1815 | 3 旅行商是np啊。
看输入规模也能看出来基本就是要优化的。。。
下面有请街霸哥给我们讲解如何用状态压缩dp解tsp。。。 |
r*****s
发帖数: 1815 | 4 掐头去尾正好16个
很明显是暗示状压到一个short。
那么对于每个节点我们分配一个二进制位。
然后对于每个节点，neng一个数组出来，数组中的ith元素记录的是一条从源点到当前
点的最短路径长度，这条最短路径经过所有i的二进制表示中置1位的节点。
于是对于某一个节点k的某一个状态i，只要把i的二进制表示里面每一个置1的位分别置
0，然后去被置0位的对应节点找对应状态，就回归到了减一规模问题。最后取最小值。
。。有点绕，我发现我这话是说不明白。
anyway，总状态数是2^16*16，状态转移计算量是16。一共是2^24 ~= 1.6e8。这个量级
是可以算的范围。
时间卡得这么好，是个竞赛题么。。
: 这就是TSP变种吧。直接暴力搜 剪枝make sense吧？
【在 z*********n 的大作中提到】
: 这就是TSP变种吧。直接暴力搜+剪枝make sense吧？
|
r*****s
发帖数: 1815 | 5 找了个舍得写字的：
http://blog.csdn.net/area_52/article/details/45967269
这类问题好像以前面试很少考，这下发现新大陆了
: 掐头去尾正好16个
: 很明显是暗示状压到一个short。
: 那么对于每个节点我们分配一个二进制位。
: 然后对于每个节点，neng一个数组出来，数组中的ith元素记录的是一条从源点
到当前
: 点的最短路径长度，这条最短路径经过所有i的二进制表示中置1位的节点。
: 于是对于某一个节点k的某一个状态i，只要把i的二进制表示里面每一个置1的位
分别置
: 0，然后去被置0位的对应节点找对应状态，就回归到了减一规模问题。最后取最
小值。
: 。。有点绕，我发现我这话是说不明白。
: anyway，总状态数是2^16*16，状态转移计算量是16。一共是2^24 ~= 1.6e8。这
个量级
: 是可以算的范围。
【在 r*****s 的大作中提到】
: 掐头去尾正好16个
: 很明显是暗示状压到一个short。
: 那么对于每个节点我们分配一个二进制位。
: 然后对于每个节点，neng一个数组出来，数组中的ith元素记录的是一条从源点到当前
: 点的最短路径长度，这条最短路径经过所有i的二进制表示中置1位的节点。
: 于是对于某一个节点k的某一个状态i，只要把i的二进制表示里面每一个置1的位分别置
: 0，然后去被置0位的对应节点找对应状态，就回归到了减一规模问题。最后取最小值。
: 。。有点绕，我发现我这话是说不明白。
: anyway，总状态数是2^16*16，状态转移计算量是16。一共是2^24 ~= 1.6e8。这个量级
: 是可以算的范围。
|
z*********n
发帖数: 1451 | 6 ls POJ大牛。状态压缩解TSP算POJ中等题了吧。 |
z*********n
发帖数: 1451 | 7 ls POJ大牛。状态压缩解TSP算POJ中等题了吧。 |
y**********u
发帖数: 2839 | |
r*****s
发帖数: 1815 | 9 这种死规矩的都是靠背套路 我觉得你们应变比我强多了。。。
: ls POJ大牛。状态压缩解TSP算POJ中等题了吧。
【在 z*********n 的大作中提到】
: ls POJ大牛。状态压缩解TSP算POJ中等题了吧。
|
