Finding the shortest path for synchronized pawns in a maze
I am going to take a guess that you are having trouble with understanding how BFS will work on this game. First, you may wonder "what is the graph we are searching on?" Let's first start with, you are not searching through the game board. This is not what you are doing at all. 

How to represent Game State

You are search through game states. I am using game state to mean:


  Game state - a full and unique description of all pieces/players in the game at the start of any "turn" during the duration of game play. A game state is final when pieces are in a position that satisfies the termination constraint.


Termination constraint as you have define is when two pawns are both able to leave the grid with the same move. You could alternatively define it as a state right after this move has been made.

Here are some examples of game states that can be uniquely describe by a $3 \times 8$ matrix $G$ where we make each entry either: Red, Blue, White, or Black.:


We would have $G_{1,1} = \text{Blue}$ and $G_{1,4} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.





We would have $G_{0,1} = \text{Blue}$ and $G_{1,3} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.





We would have $G_{0,6} = \text{Blue}$ and $G_{1,1} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.




One important thing to note here is that the only thing changing in these game states is the location of Red and Blue, everything else stays the same. This should give you some indication that we only need to maintain the location of Red and Blue to get a unique description of the game state. With this idea, we can represent all three of the prior games states as:


$\text{Blue} = (1,1)$ and $\text{Red} = (1,4)$
$\text{Blue} = (0,1)$ and $\text{Red} = (1,3)$
$\text{Blue} = (0,6)$ and $\text{Red} = (1,1)$


To be concise I will represent them as pairs of coordinates:


State = $[(1,1), (1,4)]$.
State = $[(0,1), (1,3)]$.
State = $[(0,6), (1,1)]$.


Another important thing to note here, is that the states do not need to be "possible" in the sense that we can always reach them from our initial state. The purpose of using these states is so that we can create a graph to BFS.



Graph Representation of Game States

To be able to properly "search" through the game states, we will make each state a node in our abstract graph. We will add an edge from state $s_1$ to state $s_2$ if we can get from state $s_1$ to state $s_2$ by moving both players either Up, Down, Left, or Right. Using our first example:

State $[(1,1), (1,4)]$ can move to:


State $[(0,1), (1,4)]$ via the Up move.
State $[(1,0), (1,3)]$ via the Left move.
State $[(1,1), (1,4)]$ via the Down move.
State $[(1,2), (1,5)]$ via the Right move.


So in a graph it would look like this:





How to BFS Game States

We will be looking for the shortest sequence of moves such that we reach a final state. For instance, $[(0,1), (0,6)]$ would be a final state because they can both move Up to leave the grid. One option would be to create the entire graph, then run the BFS from our start node. However, this can be costly. We can instead generate nodes adjacent to our current node on demand. We can also check if we reach a final state on demand. We need to also make sure we cannot visit "invalid" board states. For instance $[(-1,1),(1,4)]$ would be invalid because "-1" is outside our bounds. $[(0,0), (1,4)]$ would also be invalid because $G_{0,0}$ is a black square and we cannot move there.

This should be enough information to get you started. I will leave the analysis up to you. A hint on the analysis would be to consider how many game states are possible as we know in the worst cases we may visit each and all of them.