https://community.topcoder.com/stat?c=problem_statement&pm=3064&rd=5869
https://github.com/keshavnandan/Topcoder/blob/master/RevolvingDoors.txt
https://www.xuebuyuan.com/zh-tw/1126297.html?mobile=0
https://github.com/keshavnandan/Topcoder/blob/master/RevolvingDoors.cpp
https://github.com/livingstonese/topcoder/blob/master/src/main/java/srm223/divsion1/RevolvingDoors.java
https://github.com/keshavnandan/Topcoder/blob/master/RevolvingDoors.txt
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
https://www.xuebuyuan.com/zh-tw/1126297.html?mobile=0
感覺這道題比前兩道應用BFS演算法的題目要難一些,不像之前的那麼直接,如果這道題目要求的是最短的頻數的話,那跟前兩道就差不多了,但這裡求的是最少旋轉門的次數,這就有點複雜了,我的思路如下:
1. 判斷當前位置是否是終點,不是則搜索由當前位置可以到達的旋轉門,並將旋轉之後的結果狀態存入LD鏈表尾。
2. 從LD鏈表中取出第一個元素作為當前狀態,重複步驟1.
遇到的問題:BFS演算法需要設置一個訪問狀態標誌,要不然會發生重複搜索同一個狀態的情況,開始的時候我只是設置了一個visited數組確定搜索可到達的旋轉門的過程不會出現重複搜索的過程,結果出現了大問題,因為搜索過程中,進入LD中的元素會有重複的,所以會進行大量的重複搜索,時間複雜度大大增加,而且遇到某些地圖還會出現無限循環的情況,如地圖示例1,而地圖示例2直接就是算半天算不出來,後來我增加了一個 isVisited函數確保進入LD的元素跟以前進入過的元素沒有重複,問題才解決了。
還有一個要注意的問題就是地圖示例的情況不是旋轉6次,而是7次,最後一次也要先旋轉門才能到達終點,開始的程序少算了這一步。
https://github.com/keshavnandan/Topcoder/blob/master/RevolvingDoors.cpp
https://github.com/livingstonese/topcoder/blob/master/src/main/java/srm223/divsion1/RevolvingDoors.java