-= Puzzle 9: Thinking With Mazes =-

You arrive at the Portal Gun Testing Facility at the dawn of the ninth day at BitFlop Laboratories, where BitFlop Laboratories is developing its latest revolutionary invention.

Naturally, before anyone lets the intern anywhere near an actual portal gun, you're placed in front of a giant observation screen.

The screen displays a top down view of a maze (your puzzle input), represented as a grid of characters.

Each tile is either:

• #: a wall.
• S: the start position of the maze.
• E: the exit position of the maze.
• .: an open space.

The maze starts at the S tile, and your goal is to reach the E tile in the shortest number of steps possible.

You can move up, down, left, or right on the open spaces, but you cannot move diagonally and you cannot move through walls.

For example:

###########
#S#.#...#.#
#.#.#.###.#
#.#.......#
#.#.#.#####
#...#.#..E#
###.#.#.###
#...#.#...#
#.###.#.#.#
#.#.....#.#
###########

The shortest path through this maze is:

1. Move down 4 steps
2. Move right 2 steps
3. Move up 2 steps
4. Move right 2 steps
5. Move down 6 steps
6. Move right 2 steps
7. Move up 4 steps
8. Move right 2 steps

Visualized on the maze:

###########
#S#.#...#.#
#v#.#.###.#
#v#>>v....#
#v#^#v#####
#>>^#v#>>E#
###.#v#^###
#...#v#^..#
#.###v#^#.#
#.#..>>^#.#
###########

This route takes 24 steps, and no shorter route exists in this example.

You also are promised cake at the end of the maze.

How many steps does the shortest path through the maze take to reach the exit?