题解 - Vijos

0
mjlyzh588 LV 3 @ 2006-11-11 18:25:03

弗洛伊德也可以过

不过判断条件要改变一下
0
May000088 LV 3 @ 2006-11-03 09:44:39

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

先用直线方程判断任意两点之间是否有其他的墙穿过，如果有，那么两个点之间是不能直接到达的，如果没有，则用一个四维数组设为TRUE，然后DP....虽然一遍过的，但是之前想了好一阵子...
0
渴望奔跑的鱼 LV 3 @ 2006-11-02 08:19:52

DP + 线段相交计算

起初用相似总是有误差~！
0
xjdx LV 6 @ 2006-11-16 12:54:44

质疑数据为什么相似要错数据的精度是不是有问题

总相差 0.1
0
BY LV 3 @ 2006-06-14 16:13:00

DP

每面墙4个关键点(首尾两个)

则每一个关键点=min{之前的每一个可行关键点+dist(这两个点)}

可行即两点连线与墙的连线在墙的缺口处
0
watergaswck LV 3 @ 2006-03-20 12:43:41

可以用定比分点的公式
0
永恒の灵魂 LV 3 @ 2006-01-26 10:41:36

（我就是那个用相似出事故的~~~~~~~~）

用dijkstra也可以

只是代码比dp长一点^_^
0
Coldwings LV 4 @ 2006-01-26 10:00:38

DP

添加两面墙 0 n+1

有一点不太了解

我用解直线方程来判断直线相交的问题AC了

不过有朋友说用相似三角就会有麻烦...

至少推荐还是解出直线方程吧...