BFS经典套路题目，AC code如下:

``````class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string>visited;
visited.insert("0000");

queue<string> q;
q.push("0000");

int step=0;
while(!q.empty())
{
//广度优先遍历,处理同一层结点
int size = q.size();

for(int i = 0;i < size;i++)
{
string elem = q.front();
q.pop();

if(elem == target) return step;
visited.insert(elem);
for(int i= 0;i < 4;i++)
{
string up = plusone(elem,i);
if(!visited.count(up))
{
q.push(up);
visited.insert(up);
}
string down = minsone(elem,i);
if(!visited.count(down))
{
q.push(down);
visited.insert(down);
}
}
}
step += 1;
}
return -1;
}
private:
string plusone(string str,int i)//数字+1
{
str[i] = str[i]=='9'?'0':str[i]+1;
return str;
}
string minsone(string str,int i)//数字-1
{
str[i] = str[i]=='0'?'9':str[i]-1;
return str;
}
};``````

``````class Solution {
public:
int openLock(vector<string>& deadends, string target) {

queue<string> q;
q.push("0000");

int step=0;
while(!q.empty())
{
//广度优先遍历,处理同一层结点
int size = q.size();

for(int i = 0;i < size;i++)
{
string elem = q.front();
q.pop();

if(elem == target) return step;
if(visited.count(elem)) continue;
visited.insert(elem);
for(int i= 0;i < 4;i++)
{
string up = plusOne(elem,i);
if(!visited.count(up))
{
q.push(up);
}
string down = downOne(elem,i);
if(!visited.count(down))
{
q.push(down);
}
}
}
step += 1;
}
return -1;
}
private:
string plusOne(string str,int i)//数字+1
{
str[i] = str[i]=='9'?'0':str[i]+1;
return str;
}
string downOne(string str,int i)//数字-1
{
str[i] = str[i]=='0'?'9':str[i]-1;
return str;
}
};``````