題目網址: http://goo.gl/S1GSv3
題意: 你想從家裡出發至學校，題目給定N條馬路，馬路的兩端點皆為整數點，且馬路只會是水平或鉛直，但是你可以任意的走(不必在整數點上)，但是不能橫向穿越兩條馬路交點(誰敢直接對角過馬路阿XDDDD)，因為你怕危險，從家裡走至學校的路途中想經過盡量少的馬路，問最少需要多少馬路。
解法: 看到此種題目，第一件事通常是先離散化，原本題目為從起點至終點，穿過最少的線段，離散化後，題目則變為從起點點格至終點點格，穿過最少的點格牆。可以想像從起點倒水，若水被牆擋住就拆掉最外面那道牆，一直拆到水碰到終點，直接使用BFS來拆牆。
(PS: 我有看到較好的方法，是把離散化後的圖，若下個點是馬路則邊權重為1，若非，則是0，求從起點至終點的最短路徑。)
TAG: BFS, 離散化
注意: NA
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽