leetcode

0 class Solution {

1 public:

2 vector<string> neighbours(const string &code) {

3 vector<string> res;

4 for (int i = 0; i < 4; i++) {

5 for (int j = -1; j <= 1; j += 2) {

6 string s = code;

7 s[i] = (code[i] - '0' + j + 10) % 10 + '0';

8 res.push_back(s);

9 }

10 }

11 return res;

12 }

13

14 int openLock(vector<string> &deadends, string target) {

15 unordered_set<string> um(deadends.begin(), deadends.end());

16 if (um.count("0000")) return -1;

17

18 queue<string> q({"0000"});

19 for (int cnt = 0; !q.empty(); ++cnt) {

20 for (int i = q.size(); i > 0; --i) {

21 string s = q.front();

22 q.pop();

23 if (s == target) return cnt;

24

25 for (string &s : neighbours(s)) {

26 if (um.count(s)) continue;

27 um.insert(s);

28 q.push(s);

29 }

30 }

31 }

32 return -1;

33 }

34 };