今天，在做queue->BFS的延申題目 open the lock后 有感而發(fā)。
該題耗時(shí)很久。大原因是因?yàn)椤稗D(zhuǎn)化”。就是將密碼鎖問(wèn)題轉(zhuǎn)換成圖的問(wèn)題，將找到target轉(zhuǎn)換為搜尋最短路徑。
很容易想到同BFS。
但是總是提示超時(shí)。
那么怎么優(yōu)化呢。首先BFS的基本架構(gòu)是定下了。其他對(duì)容器數(shù)據(jù)的遍歷、搜索，無(wú)非就是轉(zhuǎn)化成哈希表，或者優(yōu)化查找復(fù)雜度。

后來(lái)，僅僅將“查詢某個(gè)元素是否在vector”中稍作修改，就AC了。
如下：

unordered_set<string> deadset(deadends.begin(), deadends.end());
if(deadset.find(s)!=deadset.end())

以前在leetcode上做題時(shí)，曾經(jīng)使用過(guò)unordered_map來(lái)降低時(shí)間復(fù)雜度。這個(gè)unordered_set應(yīng)該差不多。

容器可以分為：

順序性容器：vector deque list (位置和加入的順序相關(guān))

關(guān)聯(lián)性容器：set multiset map multimap（插入的元素按照特定的排序規(guī)則，與插入的先后無(wú)關(guān)）

unorder_map和unorded_set是c++11中的新的關(guān)聯(lián)性容器。

open the lock:
你有一個(gè)帶有四個(gè)圓形撥輪的轉(zhuǎn)盤(pán)鎖。每個(gè)撥輪都有10個(gè)數(shù)字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每個(gè)撥輪可以自由旋轉(zhuǎn)：例如把 '9' 變?yōu)? '0'，'0' 變?yōu)?'9' 。每次旋轉(zhuǎn)都只能旋轉(zhuǎn)一個(gè)撥輪的一位數(shù)字。
鎖的初始數(shù)字為 '0000' ，一個(gè)代表四個(gè)撥輪的數(shù)字的字符串。
列表 deadends 包含了一組死亡數(shù)字，一旦撥輪的數(shù)字和列表里的任何一個(gè)元素相同，這個(gè)鎖將會(huì)被永久鎖定，無(wú)法再被旋轉(zhuǎn)。
字符串 target 代表可以解鎖的數(shù)字，你需要給出最小的旋轉(zhuǎn)次數(shù)，如果無(wú)論如何不能解鎖，返回 -1。

class Solution {
bool visisted[10000]={false};
int dis[10000]={0};

vector<string> cal(string start) {
    vector<string> ret;
    string s=start;
    for (int i = 0; i < 4; i++) {
      s=start;
        int o = int(s.at(i)) - (int) ('0');
        for (int j = 1; j < 10; j = j + 8) {
            char n = (char) ((o + j) % 10 + '0');
            string news = s.replace(i, 1, string(1, n));
            ret.push_back(news);
        }
    }
    return ret;
}
int trans(string s) {
    int ele=1000*((int)(s[0]) - (int) ('0'))+100*((int)(s[1]) - (int) ('0'))+10*((int)(s[2]) - (int) ('0'))+((int)(s[3]) - (int) ('0'));
    return ele;
}
public:
    int openLock(vector<string>& deadends, string target) {
    string start="0000";
    queue<string> quq;
    quq.push(start);
    dis[trans(start)]=0;
    visisted[trans(start)]=true;
    unordered_set<string> deadset(deadends.begin(), deadends.end());

    while(!quq.empty()){
        string s=quq.front();
        quq.pop();
        if(deadset.find(s)!=deadset.end()) {  //found dead elements
                continue;
        }
        int v=trans(s);
    
        vector<string> relations=cal(s);
        for(vector<string>::iterator it=relations.begin();it!=relations.end();it++){
            int ele=trans(*it);
            if(!visisted[ele]) {
                visisted[ele]=true;
                dis[ele]=dis[v]+1;
                if(*it==target){
                    return dis[ele];
                }
                quq.push(*it);
            }
        }
        
    }
    return -1;   
    }
    
       
};