SRM478 Div1 Easy

250
ただのBFS

class CarrotJumping {
public:
  int theJump(int init) 
  {
    const lli mod = 1000000007;
    map<lli, int> cost;

    queue<lli> q;
    for (q.push(init % mod); q.size(); q.pop()) {
      lli x = q.front();
      if (cost[x] == 100000) continue;
      lli n = (4LL * x + 3LL) % mod;
      lli m = (8LL * x + 7LL) % mod;
      if (!cost.count(n)) {
        cost[n] = cost[x] + 1;
        q.push(n);
      }
      if (!cost.count(m)) {
        cost[m] = cost[x] + 1;
        q.push(m);
      }
    }
    
    if (cost.count(0)) ;  else cost[0] = -1;
    return cost[0];
  }

};