cafelier@SRM

SRM443 600

あとで | 14:14 |

tanakhことhaskell_masterさんの解説を参考に。なるほどなあ。ほとんど普通のBFSのコードのまま綺麗に書ける。かっこいい。全く別のアプローチとしてLayCurseさんの(要ログイン)が更にかっこよすぎる。useがその式になる理由が理解できてないのでちゃんと考えなくては…。

class BinaryFlips { public:
  int minimalMoves(int A, int B, int K) 
  {
    vector<int> visitedUpto(A+B+1, -1);
    visitedUpto[B] = B;

    // Breadth-first search from the initial state (A,B)
    queue< pair<int,int> > q;
    q.push( make_pair(B, 0) );
    while( !q.empty() )
    {
      // pop state (a,b)
      int b=q.front().first, a=A+B-b, step=q.front().second; q.pop();

      // if (a,b) == (0,A+B), done
      if( b == A+B )
        return step;

      // for all possible next values (nb) of b...
      int nb_min = abs(b-K), nb_max = A+B-abs(a-K);
      for(int nb=nb_min; nb<=nb_max; nb+=2)
        if( visitedUpto[nb] == -1 )
        {
          // if not visited, push the new state to the queue
          q.push( make_pair(nb, step+1) );
          visitedUpto[nb] = nb_max;
        }
        else
        {
          // if visited, skip it
          int nb2 = visitedUpto[nb];
          visitedUpto[nb] = max(visitedUpto[nb], nb_max);
          nb = nb2;
        }
    }
    return -1;
  }
};