# Easy to Understand(BFS+queue)

• C++:
First, extend(int) helps us explore the next states. Then, queue is used to store the valid states.
'''

``````vector<int> extend(int x){
vector<int> ans;
int t = 1;
for(int i = 0; i< 4; ++i){
int w = x/t%10;
ans.push_back(x-w*t+(w+1)%10*t);
ans.push_back(x-w*t+(w+9)%10*t);
t*=10;
}
return ans;
}
int openLock(vector<string>& deadends, string target) {

vector<bool> states(10000, false);

for(int i = 0; i< deadends.size(); i++){
int x = (d[0]-'0')*1000 + (d[1] - '0')*100 + (d[2] - '0')*10 + (d[3] - '0');
states[x] = true;
}

int t = (target[0] - '0')*1000 + (target[1] - '0')*100 + (target[2] - '0')*10 + (target[3] - '0');
queue<int> q;
if(!states[0]) q.push(0);
states[0] =  true;
int ans = -1;
int step = 0;
while(!q.empty()){
int n = q.size();
while(n--){
int x = q.front(); q.pop();
if(x == t) { ans = step; break;}
vector<int> vec = extend(x);
for(int i = 0; i<8; ++i){
if(!states[vec[i]]){
states[vec[i]] = true;
q.push(vec[i]);
}

}
}
if(ans >= 0) break; step++;
}
return ans;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.