leetcode 752. Open the Lock 打开转盘锁

Problem: 752. Open the Lock 打开转盘锁

解题过程

队列，两种可能的，某个字符+1取模或者-1+10取模，共4个字符，所以共4*2种可能，而且0000到9999共10000种可能，所以集合不大的，可以用广度优先搜索，然后判断是否已经遍历过，若是没有则放入队列，队列每次pop一个就将这个字符串放入已经遍历过的集合中，防止重复的

Code

class Solution { public: int openLock(vector<string>& deadends, string target) { if(target=="0000") return 0; queue<pair<string, int>> qe; qe.push({"0000", 0}); unordered_set<string> dead; for(string& s : deadends) { dead.insert(s); } if(dead.find("0000")!=dead.end()) return -1; pair<string, int> pr; string str, tmp; char a,b,c,d; int a1, b1,c1,d1, len; while(!qe.empty()) { int sz = qe.size(); for(int i = 0; i < sz; i++) { pr = qe.front(); str = pr.first; len = pr.second; qe.pop(); dead.insert(str); a1 = str[0]-'0'; b1 = str[1]-'0'; c1 = str[2]-'0'; d1 = str[3]-'0'; a = (a1+1)%10 + '0'; tmp.clear(); tmp += a; tmp += str[1]; tmp += str[2]; tmp += str[3]; if(dead.find(tmp)==dead.end()) { if(tmp==target) return len + 1; dead.insert(tmp); qe.push({tmp, len + 1}); } a = (a1-1+10)%10 + '0'; tmp.clear(); tmp += a; tmp += str[1]; tmp += str[2]; tmp += str[3]; if(dead.find(tmp)==dead.end()) { if(tmp==target) return len + 1; dead.insert(tmp); qe.push({tmp, len + 1}); } b = (b1+1)%10 + '0'; tmp.clear(); tmp += str[0]; tmp += b; tmp += str[2]; tmp += str[3]; if(dead.find(tmp)==dead.end()) { if(tmp==target) return len + 1; dead.insert(tmp); qe.push({tmp, len + 1}); } b = (b1-1+10)%10 + '0'; tmp.clear(); tmp += str[0]; tmp += b; tmp += str[2]; tmp += str[3]; if(dead.find(tmp)==dead.end()) { if(tmp==target) return len + 1; dead.insert(tmp); qe.push({tmp, len + 1}); } c = (c1+1)%10 + '0'; tmp.clear(); tmp += str[0]; tmp += str[1]; tmp += c; tmp += str[3]; if(dead.find(tmp)==dead.end()) { if(tmp==target) return len + 1; dead.insert(tmp); qe.push({tmp, len + 1}); } c = (c1-1+10)%10 + '0'; tmp.clear(); tmp += str[0]; tmp += str[1]; tmp += c; tmp += str[3]; if(dead.find(tmp)==dead.end()) { if(tmp==target) return len + 1; dead.insert(tmp); qe.push({tmp, len + 1}); } d = (d1+1)%10 + '0'; tmp.clear(); tmp += str[0]; tmp += str[1]; tmp += str[2]; tmp += d; if(dead.find(tmp)==dead.end()) { if(tmp==target) return len + 1; dead.insert(tmp); qe.push({tmp, len + 1}); } d = (d1-1+10)%10 + '0'; tmp.clear(); tmp += str[0]; tmp += str[1]; tmp += str[2]; tmp += d; if(dead.find(tmp)==dead.end()) { if(tmp==target) return len + 1; dead.insert(tmp); qe.push({tmp, len + 1}); } } } return -1; } };