Once again, you are stuck in a rectangular maze, represented by a String[] maze. Each character in each element of maze represents one room. Each room, naturally, has four sides, and each side may or may not have a door. The character representing the room will denote the set of doors present in that room. There will be four types of rooms: 'A' denotes a room with all four doors present, 'B' denotes a room with no doors, 'C' denotes a room with only north and south doors, and 'D' denotes a room with only east and west doors. The directions are chosen so that each element of maze represents a row of rooms from west to east, and those rows are ordered from north to south in maze.
You can move around the maze by walking from one room to one of the four adjacent rooms. However, you can do that only if both the room you are in and the room you are going into have the corresponding doors. For example, you can only move to the north if your room has a north door and the room to the north has a south door. The maze is surrounded by a solid wall, so you can never walk out of it, even if there's a door in a border room leading out. Every movement from one room to another takes 1 second.
The rooms having not enough doors may seriously constrain your movement in the maze. Luckily, you've been given a remote control that can change the maze. The remote control has only one button, and pressing this button makes all the rooms in the same row as your room and all the rooms in the same column as your room rotate 90 degress clockwise. Your room itself rotates twice; notice that a double rotation has the same effect as the room not being rotated at all. When a room rotates 90 degrees clockwise, its north door (or absence of such) becomes its east door (or absence of such), east becomes south, south becomes west and west becomes north. Operating the remote control also takes 1 second.
Return the least number of seconds required to get from the room at the northwest corner of the maze to the room at the southeast corner. If there's no way to achieve that, return -1. |