752. 打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
题解：
就bfs，枚举每个位置，正向旋转和逆向旋转的状态，注意就是开始，直接返回结果的边界条件
学习要点： string
代码：
class Solution { public: int openLock(vector<string>& deadends, string target) { queue<string> Q; string s="0000"; int targetnum=stoi(target); int f[10000]; memset(f,0,sizeof(f)); // 是这个问题，就算不是全局变量，也需要初始化，否则提交会出现错误答案。 for(auto i: deadends) f[stoi(i)]=-1; if (f[targetnum]==-1 || f[0]==-1) return -1; // 如果目标和起点都属于死亡数字，就返回-1 容易忽略 if (targetnum==0) return 0; f[0]=1; Q.push(s); while(!Q.empty()) { string p=Q.front(); Q.pop(); for(int i=0;i<4;i++) { string p1=p; // 正向旋转 if(p1[i]<'9') p1[i]=p1[i]+1; else p1[i]='0'; if(f[stoi(p1)]==0) { Q.push(p1); f[stoi(p1)]=f[stoi(p)]+1; } if (f[targetnum]>0) break; // 反向旋转 p1=p; if (p1[i]>'0') p1[i]=p1[i]-1; else p1[i]='9'; if(f[stoi(p1)]==0) { Q.push(p1); f[stoi(p1)]=f[stoi(p)]+1; } if (f[targetnum]>0) break; } if (f[targetnum]>0) break; } return f[targetnum]-1; } };