問題
http://community.topcoder.com/stat?c=problem_statement&pm=11022&rd=14187
解き方
４x＊３を３回繰り返したときに８x＋７の２回繰り替えしたものと一致するため
探索回数は最大３０００００回となる。
この回数であれば全探索可能であるので、すべての点を調べればよい。
BFSを使えばキューのため更新箇所はつねに最短となるため、
各位置での値の更新は不要となる。
コード
map<long long,int> m;
class CarrotJumping {
public: int theJump(int init) {
int MOD=1000000007;
m.clear();
m[init]=0;
queue<long long> q;
q.push(init);
while(!q.empty()){
long long x=q.front();
q.pop();
if(m[x]>100000||x==0)break;
if(m.find((x*4+3)%MOD)==m.end()){
q.push((x*4+3)%MOD);
m[(x*4+3)%MOD]=m[x]+1;
}
if(m.find((x*8+7)%MOD)==m.end()){
q.push((x*8+7)%MOD);
m[(x*8+7)%MOD]=m[x]+1;
}
}
return m[0]>100000||m[0]==0 ? -1 : m[0];
}
};
class CarrotJumping {
public: int theJump(int init) {
int MOD=1000000007;
m.clear();
m[init]=0;
queue<long long> q;
q.push(init);
while(!q.empty()){
long long x=q.front();
q.pop();
if(m[x]>100000||x==0)break;
if(m.find((x*4+3)%MOD)==m.end()){
q.push((x*4+3)%MOD);
m[(x*4+3)%MOD]=m[x]+1;
}
if(m.find((x*8+7)%MOD)==m.end()){
q.push((x*8+7)%MOD);
m[(x*8+7)%MOD]=m[x]+1;
}
}
return m[0]>100000||m[0]==0 ? -1 : m[0];
}
};