#D9630. Rolling Block
Rolling Block
Rolling Block
Problem
Rolling Block is a game in which a rectangular parallelepiped metal body is rotated and moved, and dropped into a hole in the goal. The condition to clear this game is to drop the metal body to the goal.
image0
About blocks From (1) in the figure below, the block is a 1 × 1 × L rectangular parallelepiped. The block can move while rotating in either the north, south, east, or west direction. However, the block cannot move beyond the stage. From (2) in the figure below, when the block is tilted sideways, it moves while rotating in this way with respect to the moving direction. From (3) in the figure below, when the block is upright, it moves while rotating in this way with respect to the moving direction. For (2) and (3), the gray block is the block before movement and the white block is the block after movement. The black arrow indicates that the block has moved in that direction. Also, the white arrow indicates that the block rotated in that direction as it moved. Dotted lines are drawn on the blocks, which are drawn to make the rotation easier to understand. (Such a dotted line is not written on the blocks actually handled in the game) image1 The figure below is a diagram to supplement the rotation of the block. Suppose there is a block like a dice where the sum of the faces is 7. The figure below shows the changes in the numbers on the top surface when this block is moved while rotating in four directions, north, south, east, and west, for the upright block and the collapsed block. (Such numbers are not written on the blocks actually handled in the game.) image2
About the stage Stages are given in an H × W two-dimensional grid (1 ≤ H, W ≤ 25). Each two-dimensional grid consists of the following types of cells.
-
"." Floor Blocks can sit on the floor.
-
"#" wall It is impossible to proceed to the wall, and it is not possible to move such that a part of the block rides on the wall.
-
Initial position of "S" block Only one character is given for the block. In the initial state, there is only an upright state.
-
"G" goal point Only one goal will appear during the stage. Also, it is only possible to reach the goal when the block is upright.
-
Special walls and switches Alphabet lowercase special wall Uppercase alphabet Switch for special walls
The special wall cannot progress when it appears, and it is not possible to move a part of the block so that it rides on the special wall. When the block rotates and stands upright and there is a switch beneath the block, that switch is pressed. When the switch is pressed, it disappears when a special wall of the same alphabet appears, and conversely it appears when it disappears. It is assumed that all special walls have appeared immediately after the start of the stage. There are a maximum of 5 types of special walls and switches that appear on one stage. The alphabet for the switch is {'A','B','C','D','E'}. The alphabet for special walls is {'a','b','c','d','e'}. The number of switches and special walls is H x W or less. A switch with the same alphabet as the special wall does not always appear on the stage. Also, a special wall with the same alphabet as the switch does not always appear on the stage.
- "^" Trap Do not ride the rectangular parallelepiped upright on the trap square.
Given the stage information and the initial position of the metal body, find the shortest effort to solve this puzzle. Output -1 if no solution exists.
Constraints
The input satisfies the following conditions.
- 1 ≤ H, W ≤ 25
- 1 <L <10
- Cell is Cell = {'A','B','C','D','E','S','G','a','b','c','d', It consists of'e','^','#','.'}.
Input
H W L Cell1-1 ... Cell1-W .. .. .. CellH-1 ... CellH-W
First, H, W, L are given. The vertical length, horizontal length, and block length of the stage are shown, respectively. Next, an H × W two-dimensional grid is given. This represents stage information.
Output
Given the stage information and the initial position of the metal body, find the shortest effort to solve this puzzle. Output -1 if no solution exists.
Examples
Input
5 5 2
#S.G# #...# #...#
Output
4
Input
5 5 2
S.G# ...# ...#
Output
4
Input
3 12 2
S..A..a..G#
Output
6
Input
3 12 2
S...A.a..G#
Output
-1
Input
7 13 3
S....#.....# .....#.....# .....#.....# ...........# ..........G#
Output
8
Input
3 12 2
S^^.^^.^^G#
Output
6
inputFormat
outputFormat
Output -1 if no solution exists.
Constraints
The input satisfies the following conditions.
- 1 ≤ H, W ≤ 25
- 1 <L <10
- Cell is Cell = {'A','B','C','D','E','S','G','a','b','c','d', It consists of'e','^','#','.'}.
Input
H W L Cell1-1 ... Cell1-W .. .. .. CellH-1 ... CellH-W
First, H, W, L are given. The vertical length, horizontal length, and block length of the stage are shown, respectively. Next, an H × W two-dimensional grid is given. This represents stage information.
Output
Given the stage information and the initial position of the metal body, find the shortest effort to solve this puzzle. Output -1 if no solution exists.
Examples
Input
5 5 2
#S.G# #...# #...#
Output
4
Input
5 5 2
S.G# ...# ...#
Output
4
Input
3 12 2
S..A..a..G#
Output
6
Input
3 12 2
S...A.a..G#
Output
-1
Input
7 13 3
S....#.....# .....#.....# .....#.....# ...........# ..........G#
Output
8
Input
3 12 2
S^^.^^.^^G#
Output
6
样例
5 5 2
#####
#S.G#
#...#
#...#
#####4