降低时间复杂度(c++中的容器)/Open the lock

今天，在做queue->BFS的延申题目 open the lock后 有感而发。
该题耗时很久。大原因是因为“转化”。就是将密码锁问题转换成图的问题，将找到target转换为搜寻最短路径。
很容易想到同BFS。
但是总是提示超时。
那么怎么优化呢。首先BFS的基本架构是定下了。其他对容器数据的遍历、搜索，无非就是转化成哈希表，或者优化查找复杂度。

后来，仅仅将“查询某个元素是否在vector”中稍作修改，就AC了。
如下：

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

以前在leetcode上做题时，曾经使用过unordered_map来降低时间复杂度。这个unordered_set应该差不多。

容器可以分为：

顺序性容器：vector deque list (位置和加入的顺序相关)

关联性容器：set multiset map multimap（插入的元素按照特定的排序规则，与插入的先后无关）

unorder_map和unorded_set是c++11中的新的关联性容器。

open the lock:
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -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;   
    }
    
       
};