[請益] SPOJ9 DIRVS

[bleed1979 (十三)]

題目網址：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
推 ledia:有 x-y=k 和 (1,5)-(16,3) 兩條線, 應該每個 scan line 都能
→ ledia:求出交點 ?
→ ledia:應該說跨越的那個整點
→ ledia:x=k 和 y=k 亦同
推 seanwu:有bound的DFS? 所以每個格子可能走不只一次嗎?
→ bleed1979:在每個格子標記了走到的次數，只能較低不能高。
→ tkcn:有什麼理由不用 BFS 而用 DFS 嗎?
推 tyu:有試過 Bresenham's line algorithm 嗎？
→ bleed1979:感謝ty和tk，我先改BFS試試看，再不行就找演算法。
→ bleed1979:在我send超過50次後，是該放棄了。無法理解題目定義的
→ bleed1979:直接可看見和intersect的定義。削邊邊角角的是否要計算
推 DJWS:每個格子都先計算好能不能看到起點或終點
→ DJWS:然後把所有可以走的格子找出來，再用 BFS 應該就可以了？
→ DJWS:看得到起點或終點，也就是中間格子的高度不會擋到視線。
→ DJWS:把每個點離起點/終點的斜率都算出來，應該可以 DP ？
→ DJWS:用 DP 求每一格的斜率最大值/最小值之類的...
→ tkcn:BFS 每個點最多也只走一次，所以先算"視線"省不到時間
→ DJWS:因為我發現地圖只有 200 x 200  所以我想關鍵應該不在 BFS
→ DJWS:比較需要的是　有好的方法可以判斷視線會不會被擋住
→ tkcn:同樓上結論 :)
→ DJWS:例如　已經有 (x,y) 到 (0,0) 之間的最大斜率
→ DJWS:就可以快速判斷出 (2x, 2y) 會不會被擋住視線...之類的東西
→ DJWS:tkcn 抱歉...我要先去吃晚餐了 XD
→ tkcn:嘗試寫這題，結果也是TLE  :X  我是用BFS+蠻快速的視線檢查
→ tkcn:所以我想，可能真的必須靠 DP 找出能走得格子再 BFS 了