你在進(jìn)行一個(gè)簡(jiǎn)化版的吃豆人游戲轰驳。你從(0, 0)點(diǎn)開(kāi)始出發(fā),你的目的地是(target[0], target[1])诊胞。地圖上有一些阻礙者燥筷,第 i 個(gè)阻礙者從(ghosts[i][0], ghosts[i][1])出發(fā)。
每一回合锈锤,你和阻礙者們*可以*同時(shí)向東驯鳖,西,南牙咏,北四個(gè)方向移動(dòng)臼隔,每次可以移動(dòng)到距離原位置1個(gè)單位的新位置。
如果你可以在任何阻礙者抓住你之前到達(dá)目的地(阻礙者可以采取任意行動(dòng)方式)妄壶,則被視為逃脫成功摔握。如果你和阻礙者同時(shí)到達(dá)了一個(gè)位置(包括目的地)都不算是逃脫成功。
當(dāng)且僅當(dāng)你有可能成功逃脫時(shí)丁寄,輸出 True氨淌。
示例 1:輸入:ghosts = [[1, 0], [0, 3]]target = [0, 1]輸出:true解釋:你可以直接一步到達(dá)目的地(0,1)泊愧,在(1, 0)或者(0, 3)位置的阻礙者都不可能抓住你。
示例 2:輸入:ghosts = [[1, 0]]target = [2, 0]輸出:false解釋:你需要走到位于(2, 0)的目的地盛正,但是在(1, 0)的阻礙者位于你和目的地之間删咱。
示例 3:輸入:ghosts = [[2, 0]]target = [1, 0]輸出:false解釋:阻礙者可以和你同時(shí)達(dá)到目的地。
說(shuō)明:
所有的點(diǎn)的坐標(biāo)值的絕對(duì)值 <=10000豪筝。
阻礙者的數(shù)量不會(huì)超過(guò)100痰滋。
基本思路:直覺(jué)只需要判斷如果阻礙者到目的地的距離小于等于玩家到目的地的距離,那么玩家就失敗了续崖。然后傻乎乎的計(jì)算兩點(diǎn)之間的直線距離(平方存儲(chǔ))敲街,還寫了長(zhǎng)長(zhǎng)一串表達(dá)式,結(jié)果提交不通過(guò)严望,生氣多艇!后來(lái)發(fā)現(xiàn)兩點(diǎn)間距離和長(zhǎng)寬分配關(guān)系很大,如:(0像吻,0)到(5峻黍,6)的距離平方為61,但是最少需要11步拨匆;而(4姆涩,-3)到(5,6)距離的平方為82涮雷,卻只需要10步阵面;
? ? ? ? ? ? ? ? 到這里忽然就發(fā)現(xiàn)我為什么要多此一舉算兩點(diǎn)距離,直接算最少步數(shù)就好了昂檠肌样刷!氣哭
代碼實(shí)現(xiàn):