Problem Statement
Nine of the cells on the board contain a triangular piece. Each piece is painted red, green, blue or yellow. The remaining tenth cell is empty. The goal of the game is to arrange the cells to match a specified goal pattern. To do this, the player can perform the following move any number of times: Choose a piece which is adjacent to an empty cell, and move the piece into that empty cell. Two cells are considered adjacent if the distance between their centers is exactly 1. An example of a valid move is shown in the following picture:
Ciel has painted the triangular pieces to form the starting pattern for the puzzle. She has also chosen the goal pattern. However, she has chosen both these patterns arbitrarily, so it's possible that the puzzle might not be solvable (i.e., it may be impossible to achieve the goal pattern from the given starting pattern using a sequence of valid moves). If this is the case, she would like to repaint the minimum possible number of pieces in the starting pattern to make the puzzle solvable.
You are given two
Return the minimum number of pieces which must be repainted in the starting pattern to make the puzzle solvable. If the puzzle is already solvable without repainting, return 0.
Definition
- Class:
- NinePuzzle
- Method:
- getMinimumCost
- Parameters:
- String, String
- Returns:
- int
- Method signature:
- int getMinimumCost(String init, String goal)
- (be sure your method is public)
Constraints
- init and goal will each contain exactly 10 characters.
- Each character of init and goal will be one of 'R', 'G', 'B', 'Y' or '*'.
- init and goal will each contain exactly one '*' character.
Examples
"BG*YRGRRYR"
"BGGY*YRRRR"
Returns: 0
No repainting is required because Ciel can achieve the goal pattern from the starting pattern in 3 moves:
"GBBB*BGBBG"
"RYYY*YRYYR"
Returns: 9
Ciel incautiously chose the starting pattern and the goal pattern, so unfortunately, she must repaint all the pieces.
"RRBR*BRBBB"
"BBRB*RBRRR"
Returns: 1
"RRRRRRRRR*"
"RRRRRRRRR*"
Returns: 0
init==goal case.(part1)
"YBB*GRGYGB"
"YBB*GRGYGB"
Returns: 0
init==goal case.(part2)
"YYBBGGGRR*"
"*RRRBBYYGG"
Returns: 1
2,2,2,3 case
"RYYGYB*YYY"
"BYBB*GBBRB"
Returns: 5
1,1,1,6 case
"YYYY*YYYYY"
"B*GGRRGBRG"
Returns: 9
"RR*GGGRRRG"
"GBGBGBGBG*"
Returns: 5
"YYYYYYYYG*"
"GYYYYYYY*G"
Returns: 1
"R*YGGRBYBR"
"R*RGYRYBBR"
Returns: 1
"RBGRYGYB*G"
"*RYGRBGYGB"
Returns: 0
"RRRGGGRRR*"
"*RRGRRGRRG"
Returns: 0
"*YRRRRRRRR"
"*RYRRRRRRR"
Returns: 0
"RRRRRRR*RR"
"BYGYBGB*YG"
Returns: 9
res=9
"GB*YBBGYGY"
"RRRRRRRRR*"
Returns: 9
"YGGGRYRG*R"
"BBBBB*BBBB"
Returns: 9
"YRYRYRYR*R"
"BBG*BBBBBB"
Returns: 9
"Y*YGGYGYYY"
"*RRBRRBRRR"
Returns: 9
"BRRYRR*RRY"
"GGGG*GGGGG"
Returns: 9
"*YYGYYYYBR"
"YY*GRYBYYB"
Returns: 1
random cases
"GBRYGYY*GG"
"GGYGGRR*BG"
Returns: 2
"YG*GRYYBYY"
"BBRGBBY*YB"
Returns: 4
"GYG*GGRYGB"
"BRBYYYYYG*"
Returns: 4
"GRGYRY*BRR"
"RGBRGRYRR*"
Returns: 1
"*GRBGYRGRR"
"GYGBYYRYG*"
Returns: 3
"GGBGGRG*GY"
"RB*YGGBRGG"
Returns: 2
"YGGR*YGYYB"
"BYRBRRGR*R"
Returns: 5
"GBGRGBY*GR"
"GGRYRBGG*R"
Returns: 1
"Y*GYYYYBRB"
"B*BGRYBBGR"
Returns: 4
"YYYY*GYYRB"
"GRGBYYB*YG"
Returns: 3
"BB*YYYGRGY"
"RRR*BYRGRR"
Returns: 5
"GBGBGY*GRB"
"G*BYRRGGGB"
Returns: 1
"G*YYBYGYGR"
"YBY*YBBRYG"
Returns: 2
"YYRBRR*GGR"
"RBRRGRYRB*"
Returns: 2
"GBGYGRYRG*"
"GGGGRGBYG*"
Returns: 2
"GGGYGB*RGR"
"RYYGB*RYGY"
Returns: 3
"BR*YBGBRYR"
"RBRR*RRGYR"
Returns: 3
"BGYGRGRYR*"
"BBGBBBG*RY"
Returns: 4
"BYY*GGRBYB"
"BRBYRGYBB*"
Returns: 2
"Y*BRRRGGYG"
"GBGGRRRYB*"
Returns: 1
"BR*GYBBGRG"
"RB*BGRYRGG"
Returns: 1
"BRGRBRRYR*"
"RB*GYGGGGG"
Returns: 5
"YYRYBBY*GR"
"YYR*BYGRYR"
Returns: 1
"RYRBR*GBGB"
"GGRRR*YGBR"
Returns: 2
"*BGGRGGGYB"
"YYBYYYRG*Y"
Returns: 5
"RYR*BGRGBY"
"RRYGYRGR*B"
Returns: 1
"YGRY*YRYRB"
"GRYGBGYG*Y"
Returns: 3
"YBBRGRRRB*"
"YYGRRY*YRB"
Returns: 3
"RYBYB*RGBR"
"BRGRGYGR*R"
Returns: 3
"YBG*RBYGRB"
"GGYBYR*BRY"
Returns: 1
{R,G,B,Y} = {2,2,2,3} cases
"R*YGBGBYBR"
"R*GYGYGBBG"
Returns: 2
"BBYGRGRY*B"
"YY*GBBRYYY"
Returns: 3
"BRYYB*RGGB"
"RRGYGBR*RR"
Returns: 3
"GBBRYR*BYG"
"BBYGYRRRB*"
Returns: 1
"*RBBYGGRBR"
"*GYYRGBRGB"
Returns: 2
"YRYBBGY*YB"
"RYRBYBG*GG"
Returns: 3
"YGBGG*BRYY"
"RBGYB*RGYG"
Returns: 1
"BGRRB*RYBB"
"*BRYGGRBGY"
Returns: 3
"YRRBRBYBG*"
"YYBRGGB*GR"
Returns: 2
"R*GGGGBGGY"
"*RGGGGBGGY"
Returns: 0
swapping at corner position R * G G G G B G G Y * R G G G G B G G Y
"RG*GGGBGGY"
"*GRGGGBGGY"
Returns: 0
R G * G G G B G G Y * G R G G G B G G Y
"RGG*GGBGGY"
"RGGBGG*GGY"
Returns: 0
R G G * G G B G G Y R G G B G G * G G Y
"RGGGGGB*GY"
"RGGGGG*BGY"
Returns: 0
R G G G G G B * G Y R G G G G G * B G Y
"RGGGG*BGGY"
"RGGGGYBGG*"
Returns: 0
R G G G G * B G G Y R G G G G Y B G G *
"RGGGGGBG*Y"
"RGGGGGBGY*"
Returns: 0
R G G G G G B G * Y R G G G G G B G Y *
"*BRRYRGRYR"
"BGGRB*BGBG"
Returns: 6
res = 6,7,8
"BBB*BRRBYY"
"*GGRYGGGBG"
Returns: 6
"B*YBBRBBBR"
"BG*YYYYYYR"
Returns: 6
"RRGRRRR*GR"
"GBBBBBBBY*"
Returns: 8
"GRGRRGRR*R"
"Y*RBYYBBYB"
Returns: 8
"RRRRGGRRG*"
"Y*YBRBYBYY"
Returns: 8
"RYGBYRBY*R"
"RGGG*GGGGY"
Returns: 6
"Y*GBYRBGRR"
"YY*YYYYYYY"
Returns: 7
"GBBGRYR*YB"
"G*GGGGRGGG"
Returns: 6
"B*BBBRBBBB"
"GYR*GGYRBB"
Returns: 6
"RRRRRRRRR*"
"GGGGGGGGG*"
Returns: 9
"BBBBGGGGR*"
"YYYYGGGGR*"
Returns: 4
"GBBB*BGBBG"
"RYYBBBBY*R"
Returns: 5
"GBBB*BGBBG"
"RYYY*YRYYR"
Returns: 9
"RRGGBBBBB*"
"RGBBBBBBB*"
Returns: 2
"BBGYYYYYY*"
"BGYYYYYYY*"
Returns: 1
"BBBGGRRRR*"
"BBGGRRRRY*"
Returns: 1
"RRBBG*GGYY"
"YY*GGGGGGG"
Returns: 4
"BBBB*RRRRR"
"RRRR*YYYYY"
Returns: 5
"*BBBBBBBRR"
"*BBBBBRRYY"
Returns: 2
"BG*YRGRRYR"
"BBBBBBBBB*"
Returns: 8
"GYYRRBBBB*"
"GYRRBBBBB*"
Returns: 1
"RRBBGG*RGR"
"GGGYYRR*RY"
Returns: 3
"RGGG*RGBYY"
"*GGGGGGGGR"
Returns: 4
"BBBBB*GGGG"
"GGGG*YYYYY"
Returns: 5