作者bleed1979 (十三)
站内Prob_Solve
标题[请益] SPOJ9 DIRVS
时间Mon Nov 22 21:45:10 2010
题目网址：
http://www.spoj.pl/problems/DIRVS/
这题的点数是0.49 (奇怪，0.5以上的我都AC了，这题却TLE)
大意是说，
从地图的起点移动到终点，地图上的每一格都有相对应的高度，
每移动一步的下一格高度只能是目前这格高度+1或-3的范围内，
在任何一步，必须连线到起点或连线到终点，确定是可见的。
(不会有特别突兀的高度挡住视线，只要看得到其中两点之中的一点就可以)
比如说，
高度 2 3 4 1 5
2可以看到4，但是2看不到5，因为以斜率计算在5的位置至少要6这麽高。
现在将问题拉到2D，
起点假设是(1, 5)，当我走到(16, 3)的时候，如果视线被挡住就不能走。
我的问题是其中的一个环节，
(1, 5)和(16, 3)画一条连线的时候，要怎麽快速的计算这条线经过那几个格子，
然後我再用经过的格子计算是否被挡住视线呢？
我TLE的第一做法是很笨的。
i跑1到16，j跑3到5，对於每个格子的
(i, j) 和 (i + 1, j + 1) 带入直线方程式，两个结果如果是异号，代表有直线通过，
同时也要判断(i + 1, j)和(i, j + 1)。
可是地图最大是200x200，这方法真的太慢，
第二做法是i跑1到16，将i带入方程式得j。在j的附近判断是否有直线通过。
还是太慢。
所以想请教是否有什麽奇特的演算法能快速求得直线经过的格子。
如果有AC的人能提点解题方法就再多谢不过了(目前我用有bound的DFS)。
Bleed
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.43.117.232
1F：推 ledia:有 x-y=k 和 (1,5)-(16,3) 两条线, 应该每个 scan line 都能 11/22 22:10
2F：→ ledia:求出交点 ? 11/22 22:10
3F：→ ledia:应该说跨越的那个整点 11/22 22:10
4F：→ ledia:x=k 和 y=k 亦同 11/22 22:10
5F：推 seanwu:有bound的DFS? 所以每个格子可能走不只一次吗? 11/23 00:48
6F：→ bleed1979:在每个格子标记了走到的次数，只能较低不能高。 11/23 05:05
7F：→ tkcn:有什麽理由不用 BFS 而用 DFS 吗? 11/23 10:30
8F：推 tyu:有试过 Bresenham's line algorithm 吗？ 11/23 10:46
9F：→ bleed1979:感谢ty和tk，我先改BFS试试看，再不行就找演算法。 11/23 13:13
10F：→ bleed1979:在我send超过50次後，是该放弃了。无法理解题目定义的 11/24 13:40
11F：→ bleed1979:直接可看见和intersect的定义。削边边角角的是否要计算 11/24 13:41
12F：推 DJWS:每个格子都先计算好能不能看到起点或终点 11/26 17:28
13F：→ DJWS:然後把所有可以走的格子找出来，再用 BFS 应该就可以了？ 11/26 17:29
14F：→ DJWS:看得到起点或终点，也就是中间格子的高度不会挡到视线。 11/26 17:33
15F：→ DJWS:把每个点离起点/终点的斜率都算出来，应该可以 DP ？ 11/26 17:34
16F：→ DJWS:用 DP 求每一格的斜率最大值/最小值之类的... 11/26 17:36
17F：→ tkcn:BFS 每个点最多也只走一次，所以先算"视线"省不到时间 11/26 17:37
18F：→ DJWS:因为我发现地图只有 200 x 200 所以我想关键应该不在 BFS 11/26 17:39
19F：→ DJWS:比较需要的是 有好的方法可以判断视线会不会被挡住 11/26 17:40
20F：→ tkcn:同楼上结论 :) 11/26 17:41
21F：→ DJWS:例如 已经有 (x,y) 到 (0,0) 之间的最大斜率 11/26 17:42
22F：→ DJWS:就可以快速判断出 (2x, 2y) 会不会被挡住视线...之类的东西 11/26 17:43
23F：→ DJWS:tkcn 抱歉...我要先去吃晚餐了 XD 11/26 17:43
24F：→ tkcn:尝试写这题，结果也是TLE :X 我是用BFS+蛮快速的视线检查 11/27 00:46
25F：→ tkcn:所以我想，可能真的必须靠 DP 找出能走得格子再 BFS 了 11/27 00:47