Length of the solution calculation in Breadth-first I'm trying to figure out how to calculate the route cost on this graph (it's the missionaries and cannibals game)

I have my definition as:

Mi = Missionary on the initial side, C = Cannibal on the initial side, B = Boat [I = Boat in the Initial Side, F = Boat on the Final Side],
Mf = Missionary on the other side of the river, Cf = Cannibal on the other side of the river
State: (Mi, Ci, B, Mf ,Cf)
Initial Status: (3, 3, I, 0,0)
Final Status: (0, 0, F, 3,3)
Status Space (All the valid statuses): 
{(3,3,I,0,0),(3,2,F,0,1),(2,2,F,1,1),(3,1,F,0,2),(3,2,I,0,1),(3,0,F,0,3),(3,1,I,0,2),(1,1,F,2,2),(2,2,I,1,1),(0,2,F,3,1),(0,3,I,3,0),(0,1,F,3,2),(0,2,I,3,1),(2,2,I,1,1),(3,2,I,0,1),(0,0,F,3,3)}


Rules:   

1.  Bote can only carry two people
2.  One person has to drive the boat
3.  Cannibals can't outnumber the missionaries or they the missionaries will be eaten. 
Cost: 1 per crossing. 


Exhaustive Search (or Brute Search):

(3, 3, I, 0, 0) -&gt; (2, 2, F, 1, 1) -&gt; (3,2,I,0,1), -&gt; (3,2,I,0,1) -&gt; (3,2,1,0,1) -&gt; (3,0,F,0,3) -&gt; (3,1,I,0,2) -&gt; (1,1,F,2,2) -&gt; (2,2,F,1,1) -&gt; (0,2,F,3,1) -&gt; (0,3,I,3,0) -&gt; (0,1,F,3,2) -&gt; (0,2,I,3,1) -&gt; (0,0,F,3,3)


According to me and the graph the route cost for Exhaustive Search would be 11.

How can I calculate the route cost for that graph for Breadth-first?

I do know that Breadth-first I have to separate the graphs on levels and it will test each node on that level against the final result (depending on the direction, clockwise, or counterclockwise) but I'm not sure if I should take each node as a crossing (I'm getting 14 as length of the solution). For instance in the image I take the crossing from (3,3,I,0,0) to (3,2,F,0,1) as 1 and then there isn't more child-nodes on that branch so I should get back to (3,3,I,0,0) in order to reach the branch of (2,2,F,1,1) this I don't know If I should count it too or not

To get 14 I'm doing. (3, 3, I, 0, 0) -&gt; (3,2,F,0,1) -&gt; (2,2,F,1,1) -&gt; (3,1,F,0,2) -&gt; (3,2,I,0,1) -&gt; (3,0,F,0,3) -&gt; (3,1,I,0,2) -&gt; (1,1,F,2,2) -&gt; (2,2,I,1,1) -&gt; (0,2,F,3,1) -&gt; (0,3,1,3,0) -&gt; (0,1,F,3,2) -&gt; (0,2,I,3,1) -&gt; (2,2,I,1,1) -&gt; (0,0,F,3,3)

Because of this doubts I have troubles calculating the Length of the solution
I do not know how your sources define "route cost" (I've never heard that term).

There are two points of view I can imagine.


Length of the solution

Once you reach a fitting leaf you have found your solution and can
   abort. The length of the solution, i.e. the number of steps you have
   to perform to get everybody across, is the length of the path from the
   root to that leaf.
Cost of the algorithm

The number of steps the algorithm has to perform is different, of 
  course; it may visit many nodes that are not part of the final 
  solution. The details depend on the specific implementation at hand.

Specifically, you seem to be concerned about backtracking out of
  dead ends. The usual way to implement BFS is using a queue which
  makes backtracking free since you don't actually do it; the next
  node to visit is already at the front of the queue.

If you don't use a queue and backtrack explicitly, well, you get 
  quadratic worst-case performance. Don't do it.