Breadth-first search program taking too long

[georgep]

I'm working on question 3a from the British Informatics Olympiad 2012: http://www.olympiad.org.uk/papers/2012/bio/round_one.html

A number can be transformed to another number if the letters in the digits of the first number are the
same as those in the second number with at most 5 letters (in total) being added or deleted. Individual
digits are spelt ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE and ZERO.

For example:
• 61 can be transformed to 26 since the letters SIXONE, with 4 changes (N and E deleted, and T and W
added), can then be arranged to TWOSIX. Note that the order of the letters does not matter.

A number ladder is a sequence of transformations that changes one number to a different number. Between
any two adjacent numbers on the ladder a valid transformation takes place. No number appears more than
once on a ladder. The size of a ladder is the number of transformations that takes place.

For example:
• 1, 90, 610 is a number ladder (of size 2) since 1 can be transformed to 90 and 90 can be transformed
to 610. There is no smaller number ladder that starts with 1 and finishes with 610 since 1 cannot be
transformed to 610.

Write a program to determine the size of smallest number ladders. Sample run
Your program should read in three lines, each containing two integers s then f,
(1 " s < f " 999). You should output three numbers (one per line), the ith of which
giving the size of the smallest number ladder (that only uses numbers between 1 and
999 inclusive) going from s to f on the ith line of the input.

My solution gives the correct answer, but for a ladder larger than 4, the program takes far too long.

For example, this gives the correct answer:

input:
250 361
34 756
18 735

output:
3
4
3

but this takes too long to produce an answer (limit is 5 seconds):

77 383
48 677
232 471

Here is the code, I hope someone can help find what is making it so slow:

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>

using namespace std;

const string digits[10] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};

class Node
{
public:
  
  int value, distance;
  Node(int v, int d){value = v; distance= d;}
  
};

vector<int> get_letters(int n)
{
  vector<int> letters(26, 0);
  
  while(n > 0)
  { 
    for(int i=0; i < (digits[n % 10]).length(); i++)
      letters[digits[n % 10][i] - 'A']++;

    n /= 10;
  }
    
  return letters;
}

bool transform(int num_a, int num_b)
{
  vector<int> a = get_letters(num_a);
  vector<int> b = get_letters(num_b);
  
  int changes=0;
  
  for(int i=0; i < 26; i++)
  {
    changes += a[i] > b[i] ? a[i] - b[i] : b[i] - a[i];
  }
  
  return changes <= 5;
}

int bfs(int root, int target)
{      
  vector<int> traversed; 
  queue<Node> q;
  
  traversed.push_back(root);
  q.push(Node(root, 0));
  
  while(!q.empty())
  {
    Node parent = q.front();  
    
    for(int t=1; t < 1000; t++)
    { 
      if(transform(parent.value, t) && !binary_search(traversed.begin(), traversed.end(), t))
      {
        if(t == target)
          return parent.distance+1;
        else
          q.push(Node(t, parent.distance+1));
      }   
    }
    
    traversed.push_back(parent.value);
    q.pop();
  }
  
  return -1;  
}

int main()
{
  int ans[3];
  int s, f;
  
  for(int i=0; i < 3; i++)
  {
    cin >> s >> f;

    ans[i] = bfs(s, f);
  } 
  
  for(int i=0; i < 3; i++) 
    cout << ans[i] << endl;
  return 0;
}

Thanks!

Edit: solved! Forgot to sort the vector of explored nodes before calling binary_search. Whoops.