首頁(yè) 猿問一個(gè)有趣的算法題：別驚動(dòng)魔王？

一個(gè)有趣的算法題：別驚動(dòng)魔王？

JavaScript

開滿天機(jī) 2019-04-13 08:45:54

題目如下：瓊斯博士在尋寶的過程中，來(lái)到了一個(gè)平面圖呈矩形的封閉房間。矩形的寬度為w，高度為h。為方便描述，我們將矩形左上角坐標(biāo)定為(0,0)，右下角坐標(biāo)定為(w,h)。房間的入口在矩形上沿的中點(diǎn)(即(w/2,0))，出口在矩形下沿的中點(diǎn)(即(w/2,h))。狡猾的魔王還放置了許多紅外探測(cè)器，一旦進(jìn)入探測(cè)器的探測(cè)半徑以內(nèi)，將觸發(fā)警報(bào)。現(xiàn)在瓊斯博士向您求助，他能否全身而退不驚動(dòng)魔王？輸入：booleanescape(intw,inth,intn,double[]x,double[]y,double[]r)w為矩形寬度，h為矩形高度，n為探測(cè)器總數(shù)。第i個(gè)探測(cè)器的坐標(biāo)為(x[i],y[i])，探測(cè)半徑為r[i]。輸出：trueorfalse

查看完整描述

2 回答

明月笑刀無(wú)情

TA貢獻(xiàn)1828條經(jīng)驗(yàn) 獲得超4個(gè)贊

想到一個(gè)簡(jiǎn)化問題的辦法不知道是不是有用...任意兩個(gè)探測(cè)器之間距離大于半徑和那么就可以通過,小于就不能,那么我們可以把不能通過的兩個(gè)探測(cè)器之間連上線,如果探測(cè)器覆蓋范圍到了墻壁,那么這個(gè)點(diǎn)和墻壁之間也連上線,后面就只需要判斷這些線和墻壁有沒有把出口和入口分開了.嗯,然后想到了這個(gè)辦法:后面的想法有點(diǎn)暴力,那就是把所有的線段交點(diǎn),包括和墻壁連線的端點(diǎn)都找出來(lái),這里不用管幾何的問題,只要管節(jié)點(diǎn)相連的問題,這樣這個(gè)問題就化簡(jiǎn)成一個(gè)圖論的問題了.1.從起點(diǎn)開始往外走,每一步看下一個(gè)節(jié)點(diǎn)和幾個(gè)節(jié)點(diǎn)相連2.如果只和本節(jié)點(diǎn)和另一個(gè)節(jié)點(diǎn)相連,走到這個(gè)節(jié)點(diǎn).3.如果下一個(gè)節(jié)點(diǎn)和兩個(gè)以上的節(jié)點(diǎn)相連,那么將這個(gè)節(jié)點(diǎn)分成兩個(gè),其中一個(gè)和其他節(jié)點(diǎn)繼續(xù)相連,另一個(gè)只和這個(gè)節(jié)點(diǎn)和其他相連的點(diǎn)中的一個(gè)相連,走到這個(gè)節(jié)點(diǎn).用這樣的辦法就可以把空間完全拆分成兩部分,這樣的循環(huán)結(jié)束條件是走到終點(diǎn)或者走回起點(diǎn),分別對(duì)應(yīng)true/false