# C++ 9ms Two-way BFS solution

• ``````class Solution {
public:
int openLock(vector<string>& deadends, string target) {
int res = 0, trg = stoi(target);
vector<bool> visited_s(10000, false), visited_e(10000, false);
for (auto &s : deadends) {
int n = stoi(s);
visited_s[n] = visited_e[n] = true;
}
if (visited_s[0]) return -1;
if (trg == 0) return res;
queue<int> q_s({0}), q_e({trg});
visited_s[0] = true; visited_e[trg] = true;

while (!q_s.empty() && !q_e.empty()) {
if (q_e.size() < q_s.size()) {
swap(q_s, q_e);
swap(visited_s, visited_e);
}
int fringe = q_s.size();
res++;
while(fringe--) {
int pass = q_s.front();
q_s.pop();
int n = pass;
for (int i = 0; i < 4; i++) {
int diff = pow(10, i);
int d = n % 10;
n /= 10;
int inc = pass + (d == 9 ? -9 * diff : diff);
if (!visited_s[inc]) {
if (visited_e[inc]) return res;
visited_s[inc] = true;
q_s.push(inc);
}
int dec = pass + (d == 0 ? 9 * diff : -diff);
if (!visited_s[dec]) {
if (visited_e[dec]) return res;
visited_s[dec] = true;
q_s.push(dec);
}
}
}
}
return -1;
}
};
``````

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