作者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