leetcode_cpp/bfs/752.cpp

/*
 * @Description:
 * @Version: 1.0
 * @Autor: zhuyijun
 * @Date: 2021-11-14 15:33:16
 * @LastEditTime: 2021-11-14 16:30:35
 */
#include <bits/stdc++.h>
using namespace std;
string plusOne(string s, int j) {
  if (s[j] == '9') {
    s[j] = '0';
  } else {
    s[j] += 1;
  }
  return s;
}

string minusOne(string s, int j) {
  if (s[j] == '0') {
    s[j] = '9';
  } else {
    s[j] -= 1;
  }
  return s;
}
int openLock(vector<string>& deadends, string target) {
  set<string> deads;
  deads.insert(deadends.begin(), deadends.end());
  //   for (string s : deadends) {
  //     deads.insert(s);
  //   }
  //记录已经穷举过得密码，防止走回头路
  set<string> visited;
  int step = 0;
  queue<string> q;
  q.push("0000");
  visited.insert("0000");
  while (!q.empty()) {
    int sz = q.size();
    for (int i = 0; i < sz; i++) {
      string cur = q.front();
      q.pop();
      cout << cur << endl;
      //判断是否达到终点
      if (deads.find(cur) != deads.end()) {
        continue;
      }
      if (cur == target) {
        return step;
      }

      for (int j = 0; j < 4; j++) {
        string up = plusOne(cur, j);
        if (visited.find(up) == visited.end()) {
          q.push(up);
          visited.insert(up);
        }
        string down = minusOne(cur, j);
        if (visited.find(down) == visited.end()) {
          q.push(down);
          visited.insert(down);
        }
      }
    }
    //增加步数
    step++;
  }
  return -1;
}
int main() {
  vector<string> deadends{"0201", "0101", "0102", "1212", "2002"};
  string s = "0202";
  cout << openLock(deadends, s);
  return 0;
}