教程分析案例1292will indiana jones get there_第1頁
教程分析案例1292will indiana jones get there_第2頁
教程分析案例1292will indiana jones get there_第3頁
教程分析案例1292will indiana jones get there_第4頁
教程分析案例1292will indiana jones get there_第5頁
全文預覽已結(jié)束

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

1、解題:Willna Jones Get There?題目來源:http解法或類型:Djikstra作者:/JudgeOnline/showproblem?problem_id=1292Willna Jones Get There?TimeLimit:1SMemory Limit:1000KTotal Submit:58 Accepted:25Descriptionna Jones is in a deserted city, annihilated during a war. Roofs of all houses have been destroyed and only portions o

2、f walls are still standing. The ground is so full ofminest the only safe way to move around the city is walkiner the remainingwalls. The misof our hero is to saverson who is trappedhe city. In orderto move betn two walls which are not connectedna Jones thought of taking n the two walls and then cros

3、swith him a wooden board which he could place bet from one to the other.Initialitions ofna Jones and the trappedare both on some section ofthe walls.Besides, walls are eitherhe direction South-North or West-East.You will be given a map of the city remains. Your misis to determine theminimum length o

4、f the wooden boardna Jones needs to carry in order to get tothe trapped.InputYour program should pros several test cases. Each test case starts winegerN indicating the number of wall sections remaininghe city (2 = N = 1000).Each of the next N lines describes a wall section. Thewall section to appear

5、 isthe section wherena Jones stands at the beginning.The second section to appearis the section where the trappedstands. Each wall section description consistsof threeegers X,Y and L (-10000 = X ,Y ,L = 0,the section is West-East, with length L; if L 0,the section is North-South, with length |L|.of

6、input is indicated by N = 0.OutputFor each test casehe input your program should produce one line of output,containing a real value representing the length of the wooden boardna Jonesmust carry. The length must be pred as a real number with two-digit preci, andthe last decimal digit must be rounded.

7、 The input will not contaest cases wheredifferenin rounding are significant.SampleInput141675222401346631823533378676652-2322-2-212-221-2-10 0 20-5 1 1050 50 1000Sample Output1.411.00SourceSoumerica 2002解題思路:1 解題的第一個任務是能夠求出任意兩條線段間的距離??刹捎梅智闆r始時設有標志符,可以辨認出兩條線之間的關序?qū)儆谝幌碌哪囊环N。 (1)兩條線段都是水平的。先固定一條線段,在觀察另一條線段

8、可能出現(xiàn)的情形。的方法求解。開如圖,圖中的黑線是固定的,紅線的位置是變化的。紅線在黑線的上方還是下方并不重要,關鍵在于其相對的左右位置。圖 1 中 距離 = 黑線左側(cè)點到紅線右側(cè)點的距離圖 2 中 距離 = 紅線左側(cè)點到黑線右側(cè)點的距離除圖 1,圖 2 外的情形,兩條線段在 x 坐標上必然有重合的部分,求距離的公式是一樣的。比如圖 3 距離 = fabs(黑線的 y 坐標 紅線的 y 坐標)(2)兩條線段都是豎直的。可同理分析。(3)一條線段是豎直的,另一條線段為水平的??梢允孪日J為判斷一下,用一個代號豎線的。另一個代號橫線。如圖,豎線用黑色表示,橫線用紅色表示。圖 4,5,6 中,紅線均在黑

9、線的左側(cè)。圖 4 距離=黑線左側(cè)點到紅線的下側(cè)點的距離圖 5 距離=黑線左側(cè)點的 x 坐標 紅線的 x 坐標圖 6 距離=黑線左側(cè)點到紅線的上側(cè)點的距離圖 7,8,9 中,紅線均在黑線的右側(cè)。同理可求得。圖 10,圖 11,圖 12 中,紅線的 x 坐標介于黑線兩端的 x 坐標之間。圖 10圖 11圖 12距離=紅線下端的 y 坐標 黑線的 y 坐標距離=0距離=黑線的 y 坐標 紅線上端的 y 坐標如此可求出任意兩條線段間的距離。2 完成此題的總?cè)蝿?。采?Djikstra 算法,將每條線段視為 Djikstra 算法中的一個點,兩點之間的權值表示原來兩條線間的距離。每個點自身的權值表示從初

10、始位置到此線段所需木板的最小長度。首先初始化各個點的權值,起始線所代表的點權值為 0,其余點的權值為各條線到起始線的距離,并標記起始點已被選過。從除起始點外的點中選出一個權值最小的點,標記第 last個點,并此點為已選。逐一從其余未選點選出一個點作為當前點,并求出 last 點到此當前點的距離 betn ,如果Betn last 點本身的權值,則 betn = last 點本身的權值。(betn 表示 從起始線出發(fā),經(jīng)過 last 線,到達 當前線所需木板的最小長度。)在將 betn 與 當前點原來的權值相比較,如果 betn 當前點原來的權值,則修改當前點的權值。如此反復進行,即從未選點中選取一個權值最小的點,記為 last 點,標記為已選點。根據(jù) last 點,修改其余未

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論