|NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.
Alice loves mazes so much that she spends most of her spare time drawing new mazes on sheets of graph paper. These mazes work as follows. Every cell is either an empty space or a wall. One of the empty cells is the starting cell and one of the other empty cells is the ending cell. To solve the maze, you must draw a path from the starting cell to the ending cell without lifting your pen. From each cell, you are only allowed to move to an empty neighboring cell. Two cells are neighbors if they share a common side.
Alice is so obsessed that she forces her friend Bob to solve her mazes over and over again. Lately, she began cheating by making her mazes unsolvable. However, Bob, being an avid cheater himself, discovered that he could solve those mazes by folding the sheet of paper until the maze became solvable. Alice did not initially like the fact that Bob had thwarted her attempts to make unsolvable mazes, but she eventually figured out that drawing mazes that can only be solved by folding the paper would be far more interesting than drawing unsolvable mazes.
Alice came up with a new method of creating mazes and a new set of rules. She now draws on both sides of the graph paper. The starting cell is always on the front, but the ending cell may be on either side. Bob must put the sheet of paper on a table with the front side facing up. On each move, he must do one of the following:
For example, consider the following case in which we can see both sides of the sheet (the back side depicted is the part of the sheet that would be visible after rotating it 180 degrees about the vertical axis):
In this case, the third vertical line from the left is used as a folding line.
After folding the paper, it is now possible to move from the starting cell to the second cell from the left in the top row. After that, the paper is unfolded.
Then, move one cell to the right and perform another fold.
Notice that you can fold up either the right or left side of the paper as long as you follow all the rules. After the second fold, the ending cell becomes visible, and it is now possible to move there.
Your task is to help Bob cheat by determining the fastest way to solve these mazes. You are given Strings frontSide and backSide, describing the front and back sides of the paper, respectively. The j-th character of the i-th element of each String represents the cell at row i, column j. Empty cells are denoted by '.', walls are denoted by '#', the starting cell is denoted by 'S' and the ending cell is denoted by 'E'. backSide describes what you would see if you flipped the paper over by rotating it 180 degrees about the vertical axis. Return the minimum number of steps required to solve the maze. If it is not possible to solve the maze, return -1 instead.
|-||frontSide and backSide will contain an equal number of elements h, where h is between 2 and 50, inclusive.|
|-||Each element of frontSide and backSide will contain an equal number of characters w, where w is between 2 and 50, inclusive.|
|-||Each element of frontSide and backSide will contain only '#', '.', 'S' or 'E' as characters.|
|-||Exactly one character in frontSide will be 'S'.|
|-||backSide will not contain any 'S' characters.|
|-||The total number of 'E' characters in frontSide and backSide will be exactly 1.|