Finding the shortest path for synchronized pawns in a maze

Question

I have been trying to wrap my head around this problem, and I just can't get it.

• We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, denoted with $X$.

• There are two pawns in different locations within the maze, their movements are synchronized and they must leave the maze (it has multiple exits) in the same move.

• If one moves and the other is up against a wall, it's a valid move and the other one stays in place.

• The goal is to write an algorithm that finds the lowest possible moves to get both out of the maze at the same time, of time complexity $\mathcal O(a^2 b^2)$.

I got some advice to use BFS for this problem, but I don't get how it would deal with all of the backtracking that has to be done. I've included two visualizations with the correct paths labeled to help explain the problem.

---

Example 1: Pawn starting positions shown as blue squares

---

Example 2: Pawn starting position shown as blue square and red square