# LeetCode Medium 752. Open the Lock

tags: leetcode

問題

• Explore
• Problems

アイデア

｢ダイアル式の鍵で，4桁の暗証番号が0000から始まったときに，targetの番号になるのに最短で何回ダイアルを回せばよいのか｣という問題です．

ただし，deadendsにある数字を経由しては行けないです．

全探索するしかなさそうです．

解法

• 0000から通ることが出来ない数字をdeadsとします．
  • この際，毎回ここを参照するのでstd::unordered_setにして参照コストを下げます．
• 同様に今までに訪れた数字をvisitedとして管理します．
• queueを使い，BFSで探索をします．
• 現在の数字を0000として，ここから始めます．
• deadsにの0000があれば，その場合は-1を返します．
• そうでないときは，探索するキューと訪れた数字に入れます．
• 後はキューにある数字を全て1つずつずらした数字を生成して，それぞれtargetと合致するかを調べます．
  • もし，visitedにあれば，続けます．
  • もし，deadsになければ，queに生成された数字を入れ，visitedにも入れます．
  • 1回ごとにresをインクリメントします．このresを答えとして返します．

計算量

deadendsの数をN，数字の桁をMとします．

• 時間計算量
  • 1つ1つ数字を見ていくコストは$O(10^M)$です．
  • 数字をdeadends･visitedで検索，追加するのは$O(1)$です．
• 空間計算量
  • deads･visitedに入れる数は$O(10^M)$です．

実際，4桁だけなのでそこまで計算量は大きくならないはずです．

C++

class Solution {
public:
  int openLock(vector<string>& deadends, string target) {
    unordered_set<string> deads(deadends.begin(), deadends.end());
    unordered_set<string> visited;
    queue<string> que;
    
    string cur = "0000";
    if (deads.find(cur) != deads.end())
      return -1;
    visited.insert(cur);
    que.push(cur);
    int res = 0;
    while (!que.empty()) {
      int size = move(que.size());
      for(auto i = 0; i < size; ++i) {
        string t = que.front();
        que.pop();
        vector<string> nums = move(num2Str(t));
        for (auto num : nums) {
          if (num == target)
            return ++res;
          if (visited.find(num) != visited.end())
            continue;
          if (deads.find(num) == deads.end()) {
            que.push(num);
            visited.insert(num);
          }
        }
      }
      ++res;
    }
    return -1;
  }
  
private:
  vector<string> num2Str(string key) {
    vector<string> res;
    for (auto i = 0; i < 4; i++) {
      string tmp = key;
      tmp[i] = (key[i] - '0' + 1) % 10 + '0';
      res.push_back(tmp);
      tmp[i] = (key[i] - '0' + 9) % 10 + '0';
      res.push_back(tmp);
    }
    return res;
  }
};