解いた問題

2/04/2012

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];
  }
};

0 件のコメント :

コメントを投稿