Re: [請益] SPOJ9 DIRVS
看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間14年前 (2010/11/27 23:31)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/3 (看更多)
花了很多時間終於 AC 這題了 Orz
我的作法是就跟我在推文說的一樣，
用 BFS 然後再對每一格檢查是否看得到起點、終點。
對於 (x1,y1) 是否看得到 (x2,y2)，
我的檢查方法是，用平面與直線求交點的方式，
平面指的是 x=x1+1, x=x1+2, ..., x=x2 (設 x2>x1)
計算出交點在哪，檢查對應那幾格有沒有障礙物。
另外我覺得有個不合理的地方，
例如下面這地圖:
3 0
0 3
在這情況裡頭，兩個 0 是可以互相看到對方的 (我肯定)
當然下面這種情況，兩個 1 也是:
3 3 0 1
1 0 3 3
y 平面也是一樣，
若兩次檢查都通過就表示兩個點存在 direct visibily
最後是關於時間的部份，
我只是盡量減少一些基本的運算，就勉強擠到合法的時間內了，
尤其我又是用 java，
所以我想這題的時間限制並沒有一開始我想的那麼嚴苛。
--
◤ ◥ ◢ ◣
T$，修好它吧。 ⊙▁⊙─ ─⊙▂⊙ 碰到問題，用SoftICE就對了！
╰ ∕皿﹨ ◥皿◤ ╯
◥█◤◢ ◥ ︶◤
Lee ◤ ︶ ◥◤ ﹨▼∕◥ T$ Chen
ＭＹＴＨＢＵＧＴＥＲＳ ◥ ◤＼◥ by dajidali
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：
4
25
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
