[請益] SPOJ9 DIRVS
看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間14年前 (2010/11/22 21:45)推噓4(4推 0噓 21→)留言25則, 6人參與討論串1/3 (看更多)
題目網址：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
推
11/22 22:10, , 1F
11/22 22:10, 1F
→
11/22 22:10, , 2F
11/22 22:10, 2F
→
11/22 22:10, , 3F
11/22 22:10, 3F
→
11/22 22:10, , 4F
11/22 22:10, 4F
推
11/23 00:48, , 5F
11/23 00:48, 5F
→
11/23 05:05, , 6F
11/23 05:05, 6F
→
11/23 10:30, , 7F
11/23 10:30, 7F
推
11/23 10:46, , 8F
11/23 10:46, 8F
→
11/23 13:13, , 9F
11/23 13:13, 9F
→
11/24 13:40, , 10F
11/24 13:40, 10F
→
11/24 13:41, , 11F
11/24 13:41, 11F
推
11/26 17:28, , 12F
11/26 17:28, 12F
→
11/26 17:29, , 13F
11/26 17:29, 13F
→
11/26 17:33, , 14F
11/26 17:33, 14F
→
11/26 17:34, , 15F
11/26 17:34, 15F
→
11/26 17:36, , 16F
11/26 17:36, 16F
→
11/26 17:37, , 17F
11/26 17:37, 17F
→
11/26 17:39, , 18F
11/26 17:39, 18F
→
11/26 17:40, , 19F
11/26 17:40, 19F
→
11/26 17:41, , 20F
11/26 17:41, 20F
→
11/26 17:42, , 21F
11/26 17:42, 21F
→
11/26 17:43, , 22F
11/26 17:43, 22F
→
11/26 17:43, , 23F
11/26 17:43, 23F
→
11/27 00:46, , 24F
11/27 00:46, 24F
→
11/27 00:47, , 25F
11/27 00:47, 25F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 3 篇)：
4
25
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
