This is a BFS shortest path problem with move restrictions. In a standard BFS problem, visiting the same square more than once is avoided, but the same square can be visited more than once, so long as it is visited in a new state. I am not sure if any of the test data features a case where the same square must be visited 3 times, or if this is even necessary.
How I approached this problem:
Since only the shortest distance is required, not the actual path, the maze that is input can be destroyed (within reason). It might be easier to store as much information as possible on the grid than make the queue bigger. How can we identify which square we are in and what state it is in? Remember, don't run over or into walls.
I solved this in .200s with 800+ lines of code.
928 Eternal Truths / Discussion
This is the discussion related to the wiki page 928 Eternal Truths.