752. Open the Lock
想老半天 覺得不會是BFS吧 然後受不了偷看安紗 BFS真可以
然後刻老半天 一堆WA
心態又崩一天 一生就這樣了
int openLock(vector<string>& deadends, string target) {
vector<int> step_cnt(10000, INT_MAX);
step_cnt[0] = 0; //0000
queue<int> q;
int tar = stoi(target);
//init dead
for(auto s : deadends)
step_cnt[stoi(s)] = -1;
// if 0000 is dead
if(step_cnt[0] != -1)
q.push(0); //0000
int unit_arr[4] = {1000, 100, 10, 1};
int unit2_arr[4] = {10000, 1000, 100, 10};
while(!q.empty())
{
int cur = q.front();
q.pop();
int step_cur = step_cnt[cur];
if(cur == tar)
return step_cnt[cur];
for(int i=0; i<4; i++)
{
// four digits
int unit = unit_arr[i];
int unit2 = unit2_arr[i];
int dig = (cur - (cur/unit2 * unit2))/unit;
int a = ((dig+1)%10)*unit + (cur%unit) + (cur/unit2)*unit2;
int b = ((dig+9)%10)*unit + (cur%unit) + (cur/unit2)*unit2;
if(step_cnt[a] == INT_MAX)
{
step_cnt[a] = step_cur+1;
q.push(a);
}
if(step_cnt[b] == INT_MAX)
{
step_cnt[b] = step_cur+1;
q.push(b);
}
}
}
return -1;
}