Solving "Aces Traffic Pack"

It has been taunting to me that one of the problem in Aces Traffic Pack stuck me there for several weeks! I have been thinking ways to solve it. Today, I finally did it, on my way home, from the garage to the high way to home...

Here it is:

First, given a state of the map/state, construct all the possible maps with the same cars. The map is 6-by-6. If you think about it, the possible states are really limited!

Second, use graph theory to solve the path to the exit! For each state, it corresponds to a vertex in a graph. For two states, if you can move one car to transit into the other state, then, they are connected. After you construct all the vertex and edges of this map, you can use shortest path to find the way out.